Comparar texto

Encontre a diferença entre dois arquivos de texto

Editor live

Recolher inalteradas

Sem quebra de linha

Layout

Nível de detalhe

Realce de sintaxe

Diffchecker Desktop A maneira mais segura de usar o Diffchecker. Obtenha o aplicativo Diffchecker Desktop: seus diffs nunca saem do seu computador!Obter Desktop

Untitled diff

Criado há 9 anosO diff nunca expira

43 remoções

Linhas
Total
Removido

Caracteres
Total
Removido

Para continuar usando este recurso, atualize para Diffchecker Pro Ver preços

157 linhas

32 adições

Linhas
Total
Adicionado

Caracteres
Total
Adicionado

Para continuar usando este recurso, atualize para Diffchecker Pro Ver preços

145 linhas

#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;

}

Diferenças salvas

Texto original

Abrir arquivo

#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 alterado

Abrir arquivo

#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;
}