Compare text

Find the difference between two text files

Real-time editor

Hide unchanged lines

Disable line wrap

Layout

Diff precision

Syntax highlighting

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 9 years agoDiff never expires

43 removals

Lines
Total
Removed

Characters
Total
Removed

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

157 lines

32 additions

Lines
Total
Added

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

}

Saved diffs

Original text

Open file

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

Changed text

Open file

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