Comparer le texte

Trouver la différence entre deux fichiers texte

Éditeur live

Cacher identiques

Sans retour à la ligne

Vue

Niveau de précision

Coloration syntaxique

Diffchecker Desktop La façon la plus sécurisée d'utiliser Diffchecker. Obtenez l'application Diffchecker Desktop : vos diffs ne quittent jamais votre ordinateur !Obtenir Desktop

Untitled diff

Créé il y a 9 ansLe diff n'expire jamais

116 suppressions

Lignes
Total
Supprimé

Caractères
Total
Supprimé

Pour continuer à utiliser cette fonctionnalité, passez à Diffchecker Pro Voir les prix

140 lignes

126 ajouts

Lignes
Total
Ajouté

Caractères
Total
Ajouté

Pour continuer à utiliser cette fonctionnalité, passez à Diffchecker Pro Voir les prix

145 lignes

#include<cstdio>

#include<bits/stdc++.h>

#include<cstring>

using namespace std;

#include<algorithm>

const int maxn= 600100;

#include<queue>

#include<vector>

#include<map>

#include<set>

#define maxn 100009

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

int dfn[maxn],low[maxn];

int type[maxn];

map<long long,int>mp;

map<int, int>mp;

void dfs(int cur,int fa)

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

{

vector<int>tmp[maxn], cr;

vis[cur]=1;

vector<int>buf;

dfn[cur]=low[cur]=++time;

bool NO[maxn];

for(int i=0;i<G[cur].size();i++)

{

int fdset(int x){

int j=G[cur][i].to;

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

if(j!=fa&&vis[j]==1)

}

low[cur]=min(low[cur],dfn[j]);

if(!vis[j])

void unset(int x, int y){

{

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

dfs(j,cur);

}

low[cur]=min(low[cur],low[j]);

if(low[j]>dfn[cur]&&type[G[cur][i].id]==0)

void doit(vector <int> &G){

{

cr.clear();

type[G[cur][i].id]=3;

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

vis[cur]=2;

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++)

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

p[i]=i;

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

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

}

{

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

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

{

edge[i].id=i+1;

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

}

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

sort(edge,edge+m,cmp);

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

int cur=0,tot=0;

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

while(cur<m)

edge[i].id=i+1;

{

}

seg[tot].l=cur;

sort(edge,edge+m,cmp);

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

int cur=0,tot=0;

cur++;

while(cur<m)

seg[tot].r=cur;

{

cur++;tot++;

seg[tot].l=cur;

}

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

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

cur++;

{

seg[tot].r=cur;

st.clear();mp.clear();

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

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

cur++;tot++;

{

}

Edge e;

int x=findset(edge[j].v);

int q;

int y=findset(edge[j].u);

scanf("%d", &q);

if(x==y)

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

{

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

type[edge[j].id]=1;continue;

cr.clear();

}

int num;

else

scanf("%d", &num);

{

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

if(x>y)swap(x,y);

int x;

long long num=(long long)x*maxn+y;

scanf("%d", &x);

if(!mp[num]){

int w = mp[c[x]];

mp[num]=edge[j].id;

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

e.to=y;e.id=edge[j].id;

tmp[w].push_back(i);

G[x].push_back(e);

tmp[w].push_back(x);

st.insert(x);

cr.push_back(w);

e.to=x;

}

G[y].push_back(e);

else{

st.insert(y);}

tmp[w].push_back(x);

else

}

{

buf.push_back(x);

type[edge[j].id]=2;

}

type[mp[num]]=2;

for(auto x: cr){

}

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

}

tmp[x].clear();

}

set<int>::iterator it;

doit(buf);

time=0;

}

for(it=st.begin();it!=st.end();++it)

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

{

if(!vis[*it])dfs(*it,-1);

check(i);

}

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

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

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

{

}

if(type[edge[j].id]==0)

}

type[edge[j].id]=2;

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

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

}

for(it=st.begin();it!=st.end();++it)

{vis[*it]=0;G[*it].clear();}

}

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

{

if(type[i]==1)printf("none\n");

if(NO[i]){

else if(type[i]==2)printf("at least one\n");

puts("NO");

else if(type[i]==3)printf("any\n");

}

else{

puts("YES");

}

return 0;

}

Différences enregistrées

Texte d'origine

Ouvrir un fichier

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
#include<set>
#define maxn 100009
using namespace std;
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 time;
int dfn[maxn],low[maxn];
int type[maxn];
map<long long,int>mp;
void dfs(int cur,int fa)
{
    vis[cur]=1;
    dfn[cur]=low[cur]=++time;
    for(int i=0;i<G[cur].size();i++)
    {
        int j=G[cur][i].to;
        if(j!=fa&&vis[j]==1)
            low[cur]=min(low[cur],dfn[j]);
        if(!vis[j])
        {
            dfs(j,cur);
            low[cur]=min(low[cur],low[j]);
            if(low[j]>dfn[cur]&&type[G[cur][i].id]==0)
            {
                type[G[cur][i].id]=3;
            }
        }
    }
    vis[cur]=2;
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        p[i]=i;
    for(int i=0;i<m;i++)
    {
        scanf("%d%d%d",&edge[i].u,&edge[i].v,&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;
        cur++;tot++;
    }
    for(int i=0;i<tot;i++)
    {
        st.clear();mp.clear();
        for(int j=seg[i].l;j<=seg[i].r;j++)
        {
            Edge e;
            int x=findset(edge[j].v);
            int y=findset(edge[j].u);
            if(x==y)
            {
                type[edge[j].id]=1;continue;
            }
            else
            {
                if(x>y)swap(x,y);
                long long num=(long long)x*maxn+y;
                if(!mp[num]){
                mp[num]=edge[j].id;
                e.to=y;e.id=edge[j].id;
                G[x].push_back(e);
                st.insert(x);
                e.to=x;
                G[y].push_back(e);
                st.insert(y);}
                else
                {
                    type[edge[j].id]=2;
                    type[mp[num]]=2;
                }
            }
        }
        set<int>::iterator it;
        time=0;
        for(it=st.begin();it!=st.end();++it)
        {
            if(!vis[*it])dfs(*it,-1);
        }
        for(int j=seg[i].l;j<=seg[i].r;j++)
        {
            if(type[edge[j].id]==0)
                type[edge[j].id]=2;
            unionset(edge[j].u,edge[j].v);
        }
        for(it=st.begin();it!=st.end();++it)
        {vis[*it]=0;G[*it].clear();}
}

for(int i=1;i<=m;i++)
    {
        if(type[i]==1)printf("none\n");
        else if(type[i]==2)printf("at least one\n");
        else if(type[i]==3)printf("any\n");
    }
}

Texte modifié

Ouvrir un fichier

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