Comparar texto

Encuentra la diferencia entre dos archivos de texto

Editor live

Ocultar sin cambios

Sin ajuste de línea

Vista

Nivel de detalle

Resaltado de sintaxis

Diffchecker Desktop La forma más segura de usar Diffchecker. ¡Obtén la app de Diffchecker Desktop: tus diffs nunca salen de tu computadora!Obtener Desktop

Untitled diff

Creado hace 9 añosEl diff nunca expira

43 eliminaciones

Líneas
Total
Eliminado

Caracteres
Total
Eliminado

Para continuar usando esta función, actualice a Diffchecker Pro Ver precios

157 líneas

32 adiciones

Líneas
Total
Añadido

Caracteres
Total
Añadido

Para continuar usando esta función, actualice a Diffchecker Pro Ver precios

145 líneas

#include <cstdio>

#include<bits/stdc++.h>

#include <cstring>

#include <algorithm>

#include <queue>

#include <iostream>

#include <vector>

#include <map>

#include <set>

#define maxn 600009

using namespace std;

int UU[maxn], VV[maxn], WW[maxn], q[maxn];

const int maxn= 600100;

using namespace std;

int a[maxn], b[maxn], c[maxn], q[maxn];

typedef struct

{

int l,r;

}node;

}node1;

node seg[maxn];

node1 seg[maxn];

typedef struct

{

int u,v,w,id;

}node1;

}node2;

node1 edge[maxn];

node2 edge[maxn];

bool cmp(node1 x,node1 y)

bool cmp(node2 x,node2 y)

{

return x.w<y.w;

}

int p[maxn];

int findset(int x)

{

return x==p[x]?x:p[x]=findset(p[x]);

}

void unionset(int x,int y)

{

p[findset(x)]=findset(y);

}

int vis[maxn];

bool wa[maxn];

set<int>st;

struct Edge

{

int to,id;

};

vector<Edge>G[maxn];

int type[maxn];

map<int, int>mp;

vector< vector<int> > V[maxn];

vector<int>tmp[maxn], cr;

vector<int>buf;

bool NO[maxn];

int fdset(int x){

return q[x] == x ? x : q[x] = fdset(q[x]);

}

void unset(int x, int y){

q[fdset(x)] = fdset(y);

}

void doit(vector <int> &G){

cr.clear();

int lb = G[0];

for(int j = 1; j < (int)G.size(); j++){

int u = UU[G[j]];

int u = a[G[j]], v = b[G[j]];

int v = VV[G[j]];

u = findset(u);v = findset(v);

u = findset(u);

v = findset(v);

if(fdset(u) == fdset(v)){

NO[lb] = 1;

}

unset(u, v);

cr.push_back(u);

cr.push_back(u);cr.push_back(v);

cr.push_back(v);

if(NO[lb])break;

if(NO[lb])

break;

}

for(auto x: cr)

for(auto x: cr)q[x] = x;

q[x] = x;

}

void check(int x){

for(int i = 0; i < (int)V[x].size(); i++){

doit(V[x][i]);

}

int main()

{

int n,m;

scanf("%d%d",&n,&m);

for(int i=1;i<=n;i++){

p[i]=i;

p[i]=i;q[i] = i;

q[i] = i;

}

for(int i=0;i<m;i++)

{

scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w);

UU[i + 1] = edge[i].u;

a[i+1] = edge[i].u;

VV[i + 1] = edge[i].v;

b[i+1] = edge[i].v;

WW[i + 1] = edge[i].w;

c[i+1] = edge[i].w;

edge[i].id=i+1;

}

sort(edge,edge+m,cmp);

int cur=0,tot=0;

while(cur<m)

{

seg[tot].l=cur;

while(cur+1<m&&edge[cur].w==edge[cur+1].w)

cur++;

seg[tot].r=cur;

mp[edge[cur].w] = tot;

cur++;tot++;

}

int Q;

int q;

scanf("%d", &Q);

scanf("%d", &q);

for(int i = 1; i <= Q; i++){

for(int i = 1; i <= q; i++){

buf.clear();

buf.clear();buf.push_back(i);

buf.push_back(i);

cr.clear();

int num;

scanf("%d", &num);

for(int j = 0; j < num; j++){

int x;

scanf("%d", &x);

int w = mp[WW[x]];

int w = mp[c[x]];

if((int)tmp[w].size() == 0){

tmp[w].push_back(i);

tmp[w].push_back(x);

cr.push_back(w);

}

else{

tmp[w].push_back(x);

}

buf.push_back(x);

}

for(auto x: cr){

V[x].push_back(tmp[x]);

tmp[x].clear();

}

doit(buf);

}

//cout << tot << endl;

for(int i=0;i<tot;i++)

{

check(i);

for(int j = seg[i].l; j <= seg[i].r; j++){

unionset(edge[j].u, edge[j].v);

}

for(int i = 1; i <= Q; i++)

for(int i = 1; i <= q; i++)

if(NO[i])

{

if(NO[i]){

puts("NO");

else

}

else{

puts("YES");

}

return 0;

}

Diferencias guardadas

Texto original

Abrir archivo

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <iostream>
#include <vector>
#include <map>
#include <set>
#define maxn 600009
using namespace std;
int UU[maxn], VV[maxn], WW[maxn], q[maxn];
typedef struct
{
	int l,r;
}node;
node seg[maxn];
typedef struct
{
	int u,v,w,id;
}node1;
node1 edge[maxn];
bool cmp(node1 x,node1 y)
{
	return x.w<y.w;
}
int p[maxn];
int findset(int x)
{
	return x==p[x]?x:p[x]=findset(p[x]);
}
void unionset(int x,int y)
{
   p[findset(x)]=findset(y);
}
int vis[maxn];
bool wa[maxn];
set<int>st;
struct Edge
{
	int to,id;
};
vector<Edge>G[maxn];
int type[maxn];
map<int, int>mp;

vector< vector<int> > V[maxn];
vector<int>tmp[maxn], cr;
vector<int>buf;
bool NO[maxn];

int fdset(int x){
	return q[x] == x ? x : q[x] = fdset(q[x]);
}

void unset(int x, int y){
	q[fdset(x)] = fdset(y);
}

void doit(vector <int> &G){
	cr.clear();
	int lb = G[0];
	for(int j = 1; j < (int)G.size(); j++){
		int u = UU[G[j]];
		int v = VV[G[j]];
		u = findset(u);
		v = findset(v);
		if(fdset(u) == fdset(v)){
			NO[lb] = 1;
		}
		unset(u, v);
		cr.push_back(u);
		cr.push_back(v);
		if(NO[lb])
			break;
	}
	for(auto x: cr)
		q[x] = x;
}

void check(int x){
	for(int i = 0; i < (int)V[x].size(); i++){
		doit(V[x][i]);
	}
}

int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		p[i]=i;
		q[i] = i;
	}
	for(int i=0;i<m;i++)
	{
		scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w);
		UU[i + 1] = edge[i].u;
		VV[i + 1] = edge[i].v;
		WW[i + 1] = edge[i].w;
		edge[i].id=i+1;
	}
	sort(edge,edge+m,cmp);
	int cur=0,tot=0;
	while(cur<m)
	{
		seg[tot].l=cur;
		while(cur+1<m&&edge[cur].w==edge[cur+1].w)
			cur++;
		seg[tot].r=cur;
		mp[edge[cur].w] = tot;
		cur++;tot++;
	}
	
	int Q;
	scanf("%d", &Q);
	for(int i = 1; i <= Q; i++){
		buf.clear();
		buf.push_back(i);
		cr.clear();
		int num;
		scanf("%d", &num);
		for(int j = 0; j < num; j++){
			int x;
			scanf("%d", &x);
			int w = mp[WW[x]];
			if((int)tmp[w].size() == 0){
				tmp[w].push_back(i);
				tmp[w].push_back(x);
				cr.push_back(w);
			}
			else{
				tmp[w].push_back(x);
			}
			buf.push_back(x);
		}
		for(auto x: cr){
			V[x].push_back(tmp[x]);
			tmp[x].clear();
		}
		doit(buf);
	}
	//cout << tot << endl;
	for(int i=0;i<tot;i++)
	{
		check(i);
		for(int j = seg[i].l; j <= seg[i].r; j++){
			unionset(edge[j].u, edge[j].v);
		}
    }	
    for(int i = 1; i <= Q; i++)
    	if(NO[i])
    		puts("NO");
    	else
    		puts("YES");
	return 0;
}

Texto modificado

Abrir archivo

#include<bits/stdc++.h>
using namespace std;
const int maxn= 600100;
using namespace std;
int a[maxn], b[maxn], c[maxn], q[maxn];
typedef struct
{
	int l,r;
}node1;
node1 seg[maxn];
typedef struct
{
	int u,v,w,id;
}node2;
node2 edge[maxn];
bool cmp(node2 x,node2 y)
{
	return x.w<y.w;
}
int p[maxn];
int findset(int x)
{
	return x==p[x]?x:p[x]=findset(p[x]);
}
void unionset(int x,int y)
{
   p[findset(x)]=findset(y);
}
int vis[maxn];
bool wa[maxn];
set<int>st;
struct Edge
{
	int to,id;
};
vector<Edge>G[maxn];
int type[maxn];
map<int, int>mp;
vector< vector<int> > V[maxn];
vector<int>tmp[maxn], cr;
vector<int>buf;
bool NO[maxn];

int fdset(int x){
	return q[x] == x ? x : q[x] = fdset(q[x]);
}

void unset(int x, int y){
	q[fdset(x)] = fdset(y);
}

void doit(vector <int> &G){
	cr.clear();
	int lb = G[0];
	for(int j = 1; j < (int)G.size(); j++){
		int u = a[G[j]], v = b[G[j]];
		u = findset(u);v = findset(v);
		if(fdset(u) == fdset(v)){
			NO[lb] = 1;
		}
		unset(u, v);
		cr.push_back(u);cr.push_back(v);
		if(NO[lb])break;
	}
	for(auto x: cr)q[x] = x;
}

void check(int x){
	for(int i = 0; i < (int)V[x].size(); i++){
		doit(V[x][i]);
	}
}

int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		p[i]=i;q[i] = i;
	}
	for(int i=0;i<m;i++)
	{
		scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w);
		a[i+1] = edge[i].u;
		b[i+1] = edge[i].v;
		c[i+1] = edge[i].w;
		edge[i].id=i+1;
	}
	sort(edge,edge+m,cmp);
	int cur=0,tot=0;
	while(cur<m)
	{
		seg[tot].l=cur;
		while(cur+1<m&&edge[cur].w==edge[cur+1].w)
			cur++;
		seg[tot].r=cur;
		mp[edge[cur].w] = tot;
		cur++;tot++;
	}
	
	int q;
	scanf("%d", &q);
	for(int i = 1; i <= q; i++){
		buf.clear();buf.push_back(i);
		cr.clear();
		int num;
		scanf("%d", &num);
		for(int j = 0; j < num; j++){
			int x;
			scanf("%d", &x);
			int w = mp[c[x]];
			if((int)tmp[w].size() == 0){
				tmp[w].push_back(i);
				tmp[w].push_back(x);
				cr.push_back(w);
			}
			else{
				tmp[w].push_back(x);
			}
			buf.push_back(x);
		}
		for(auto x: cr){
			V[x].push_back(tmp[x]);
			tmp[x].clear();
		}
		doit(buf);
	}
	for(int i=0;i<tot;i++)
	{
		check(i);
		for(int j = seg[i].l; j <= seg[i].r; j++){
			unionset(edge[j].u, edge[j].v);
		}
    }	
    for(int i = 1; i <= q; i++)
    {
    	if(NO[i]){
    		puts("NO");
		}   		
    	else{
    		puts("YES");
		}	
	}	
	return 0;
}