Untitled diff
Erstellt Diff läuft nie ab
116 Entfernungen
| Zeilen | |
|---|---|
| Gesamt | |
| Entfernt | |
| Zeichen | |
| Gesamt | |
| Entfernt | |
126 Hinzufügungen
| Zeilen | |
|---|---|
| Gesamt | |
| Hinzugefügt | |
| Zeichen | |
| Gesamt | |
| Hinzugefügt | |
#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;
using namespace std;
int a[maxn], b[maxn], c[maxn], q[maxn];
typedef struct
typedef struct
{
{
int l,r;
int l,r;
}node;
}node1;
node seg[maxn];
node1 seg[maxn];
typedef struct
typedef struct
{
{
int u,v,w,id;
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;
return x.w<y.w;
}
}
int p[maxn];
int p[maxn];
int findset(int x)
int findset(int x)
{
{
return x==p[x]?x:p[x]=findset(p[x]);
return x==p[x]?x:p[x]=findset(p[x]);
}
}
void unionset(int x,int y)
void unionset(int x,int y)
{
{
p[findset(x)]=findset(y);
p[findset(x)]=findset(y);
}
}
int vis[maxn];
int vis[maxn];
bool wa[maxn];
bool wa[maxn];
set<int>st;
set<int>st;
struct Edge
struct Edge
{
{
int to,id;
int to,id;
};
};
vector<Edge>G[maxn];
vector<Edge>G[maxn];
int time;
int dfn[maxn],low[maxn];
int type[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 main()
{
{
int n,m;
int n,m;
scanf("%d%d",&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;
}
}