Comparar texto

Encontre a diferença entre dois arquivos de texto

Real-time diff

Unified diff

Collapse lines

Highlight change

Syntax highlighting

Ferramentas

Diffchecker Desktop The most secure way to run Diffchecker. Get the Diffchecker Desktop app: your diffs never leave your computer!Get Desktop

Untitled diff

Created 8 years agoDiff never expires

Lines
Total
Removed

Words
Total
Removed

To continue using this feature, upgrade to Diffchecker Pro View Pricing

157 lines

Lines
Total
Added

Words
Total
Added

To continue using this feature, upgrade to Diffchecker Pro View Pricing

145 lines

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

}

Diffs salvos

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