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

116 eliminaciones

Líneas
Total
Eliminado

Caracteres
Total
Eliminado

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

140 líneas

126 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>

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;

}

Diferencias guardadas

Texto original

Abrir archivo

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

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