Untitled diff
Erstellt Diff läuft nie ab
114 Entfernungen
| Zeilen | |
|---|---|
| Gesamt | |
| Entfernt | |
| Zeichen | |
| Gesamt | |
| Entfernt | |
122 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])
{
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;
}
}
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;
}
}
vis[cur]=2;
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);
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;
edge[i].id=i+1;
}
}
sort(edge,edge+m,cmp);
sort(edge,edge+m,cmp);
int cur=0,tot=0;
int cur=0,tot=0;
while(cur<m)
while(cur<m)
{
{
seg[tot].l=cur;
seg[tot].l=cur;
while(cur+1<m&&edge[cur].w==edge[cur+1].w)
while(cur+1<m&&edge[cur].w==edge[cur+1].w)
cur++;
cur++;
seg[tot].r=cur;
seg[tot].r=cur;
mp[edge[cur].w] = tot;
cur++;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++)
for(int i=0;i<tot;i++)
{
{
st.clear();mp.clear();
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);
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;
for(int i = 1; i <= q; i++)
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)
if(NO[i]){
type[edge[j].id]=2;
puts("NO");
unionset(edge[j].u,edge[j].v);
}
}
for(it=st.begin();it!=st.end();++it)
else{
{vis[*it]=0;G[*it].clear();}
puts("YES");
}
}
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");
}
}
return 0;
}
}