//DM
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <queue>
//#define death
#ifndef death
#include "simurgh.h"
#endif // death
#define LL long long
#define mod 1000000007ll
#define MP make_pair
#define PB push_back
#define all(v) v.begin(),v.end()
using namespace std;
#ifdef death
int count_common_roads(vector<int> a){
for(int i=0;i<a.size();i++)
cout<<a[i]<<" ";
cout<<"!\n";
int ans;
cin>>ans;
return ans;
}
#endif //death
int n,m,used[502],cnt,fnd[502],tin[502],timer;
vector<int> g[502];
map<pair<int,int>,int> id;
vector<int> backs[502],ans,print;
pair<int,int> edge[502];
void answer(int a)
{
if(fnd[a])
return;
fnd[a]=1;
ans.PB(a);
}
int get(int old,int nw)
{
vector<int> x=print;
for(int i=0;i<x.size();i++)
if(x[i]==old)
x[i]=nw;
return count_common_roads(x);
}
void dfs1(int v,int p=-1)
{
used[v]=1;
tin[v]=++timer;
for(int i=0;i<g[v].size();i++)
{
int to=g[v][i];
if(to==p)
continue;
if(used[to])
{
backs[v].PB(id[MP(v,to)]);
continue;
}
print.PB(id[MP(v,to)]);
dfs1(to,v);
}
}
void dfs(int v,int p=-1)
{
if(ans.size()==n-1)
return;
used[v]=1;
for(int i=0;i<g[v].size();i++)
{
int to=g[v][i];
if(used[to])
continue;
dfs(to,v);
}
if(p==-1)
return;
if(ans.size()==n-1)
return;
int rad=id[MP(p,v)];
//cout<<"from "<<v<<endl;
random_shuffle(all(backs[v]));
int qanak=0;
for(int i=0;i<backs[v].size();i++)
{
int a,b;
a=edge[backs[v][i]].first;
b=edge[backs[v][i]].second;
if(min(tin[a],tin[b])>=tin[v])
continue;
backs[p].PB(backs[v][i]);
int newcnt=get(rad,backs[v][i]);
if(newcnt>cnt)
{
answer(backs[v][i]);
qanak++;
}
else if(newcnt<cnt)
{
answer(rad);
qanak++;
break;
}
if(ans.size()==n-1)
return;
}
backs[v].clear();
if(qanak==0)
answer(rad);
}
vector<int> find_roads(int N,vector<int> U,vector<int> V)
{
srand(6446546);
n=N;
m=U.size();
for(int i=0;i<m;i++)
{
int a=U[i];
int b=V[i];
edge[i]=MP(a,b);
id[MP(a,b)]=id[MP(b,a)]=i;
g[a].PB(b);
g[b].PB(a);
}
int start=(rand()%n);
dfs1(start);
for(int i=0;i<n;i++)
used[i]=0;
cnt=count_common_roads(print);
dfs(start);
return ans;
}
#ifdef death
int main()
{
int N,M;
vector<int> U,V;
cin>>N>>M;
for(int i=0;i<M;i++)
{
int a,b;
cin>>a>>b;
U.PB(a);
V.PB(b);
}
vector<int> ANS=find_roads(N,U,V);
cout<<"!!!!\n";
for(int i=0;i<ANS.size();i++)
{
cout<<U[ANS[i]]<<":"<<V[ANS[i]]<<endl;
}
return 0;
}
#endif // death
/*
7 21
2 0
0 1
5 2
2 6
1 3
3 0
6 0
4 5
3 2
4 0
1 4
0 5
4 3
4 6
6 1
2 1
5 3
2 4
5 6
5 1
6 3
6 9
0 1
1 2
2 0
2 3
3 4
3 5
4 5
0 4
1 5
4 6
0 1
0 2
0 3
1 2
1 3
2 3
*/
Compilation message
simurgh.cpp: In function 'int get(int, int)':
simurgh.cpp:54:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<x.size();i++)
~^~~~~~~~~
simurgh.cpp: In function 'void dfs1(int, int)':
simurgh.cpp:64:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<g[v].size();i++)
~^~~~~~~~~~~~
simurgh.cpp: In function 'void dfs(int, int)':
simurgh.cpp:81:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(ans.size()==n-1)
~~~~~~~~~~^~~~~
simurgh.cpp:84:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<g[v].size();i++)
~^~~~~~~~~~~~
simurgh.cpp:92:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
if(p==-1)
^~
simurgh.cpp:94:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
if(ans.size()==n-1)
^~
simurgh.cpp:94:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(ans.size()==n-1)
~~~~~~~~~~^~~~~
simurgh.cpp:100:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<backs[v].size();i++)
~^~~~~~~~~~~~~~~~
simurgh.cpp:120:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(ans.size()==n-1)
~~~~~~~~~~^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
correct |
| 2 |
Correct |
2 ms |
376 KB |
correct |
| 3 |
Runtime error |
24 ms |
3716 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
