| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 719227 |
2023-04-05T16:34:52 Z |
bin9638 |
Simurgh (IOI17_simurgh) |
C++17 |
|
6 ms |
4564 KB |
#include <bits/stdc++.h>
#ifndef SKY
#include "simurgh.h"
#endif // SKY
using namespace std;
#define N 510
#define ll long long
#define fs first
#define sc second
#define ii pair<int,int>
#define pb push_back
int pos[N*N],tmp[N],n,m,times,ktr[N*N],par_id[N];
ii cnt[N],canh[N*N];
vector<ii>g[N];
vector<int>lis;
struct DSU
{
int lab[N];
void init()
{
memset(lab,-1,sizeof(lab));
}
int root(int u)
{
if(lab[u]<0)
return u;
return(lab[u]=root(lab[u]));
}
bool update(int u,int v)
{
if((u=root(u))==(v=root(v)))
return 0;
if(lab[u]>lab[v])
swap(u,v);
lab[u]+=lab[v];
lab[v]=u;
return 1;
}
}T;
#ifdef SKY
int chon[N*N];
int count_common_roads(vector<int>r)
{
int res=0;
for(auto i:r)
res+=chon[i];
return res;
}
#endif // SKY
int query=0;
int my_ask(vector<int>r)
{
assert(r.size()==n-1);
query++;
// assert(query<=8000);
return count_common_roads(r);
}
void DFS(int u,int p)
{
cnt[u].fs=++times;
for(auto v:g[u])
if(v.fs!=p)
{
par_id[v.fs]=v.sc;
DFS(v.fs,u);
}
cnt[u].sc=times;
}
bool tren(int u,int v)
{
return (cnt[u].fs<=cnt[v].fs&&cnt[u].sc>=cnt[v].sc);
}
ii get_cnt(int u,int v)
{
ii res={0,0};
for(int i=0;i<n;i++)
if(tren(i,u)+tren(i,v)==1)
{
if(ktr[par_id[i]]==-1)
res.fs++;
else res.sc++;
}
return res;
}
void solve(vector<int>s)
{
if(s.empty())
return;
vector<int>hoi;
T.init();
for(auto u:s)
T.update(canh[u].fs,canh[u].sc),hoi.pb(u);
for(int i=0;i<m;i++)
if(ktr[i]==-1&&pos[i]==0&&T.update(canh[i].fs,canh[i].sc))
{
s.pb(i);
pos[i]=1;
}
int val=0;
for(auto i:lis)
if(T.update(canh[i].fs,canh[i].sc))
val+=ktr[i],hoi.pb(i);
int my_ans=my_ask(hoi);
if(val==my_ans)
{
for(auto u:s)
ktr[u]=0;
return;
}
if(val+s.size()==my_ans)
{
for(auto u:s)
ktr[u]=1;
return;
}
if(s.size()==1)
{
ktr[s[0]]=1;
return;
}
vector<int>L,R;
for(int i=0;i<s.size();i++)
if(i*2<s.size())
L.pb(s[i]);
else R.pb(s[i]);
solve(L);
solve(R);
}
vector<int> find_roads(int cc, vector<int> canh_fs, vector<int> canh_sc)
{
n=cc;
m=canh_fs.size();
for(int i=0;i<m;i++)
canh[i]={canh_fs[i],canh_sc[i]};
memset(ktr,-1,sizeof(ktr));
T.init();
for(int i=0;i<m;i++)
if(T.update(canh[i].fs,canh[i].sc))
{
lis.pb(i);
// cout<<i<<endl;
g[canh[i].fs].pb({canh[i].sc,i});
g[canh[i].sc].pb({canh[i].fs,i});
}
memset(par_id,-1,sizeof(par_id));
DFS(0,-1);
int val=my_ask(lis);
//cout<<val<<endl;
for(int i=0;i<m;i++)
{
ii cc=get_cnt(canh[i].fs,canh[i].sc);
if(cc.fs>0&&cc.fs+cc.sc>1)
{
int u=canh[i].fs,v=canh[i].sc;
if(cc.sc==0)
{
int kt=0;
for(int j=0;j<n;j++)
if(tren(j,u)+tren(j,v)==1)
{
vector<int>luu=lis;
for(int t=0;t<n-1;t++)
if(luu[t]==par_id[j])
luu[t]=i;
tmp[j]=my_ask(luu);
if(tmp[j]>val)
kt=1;
}
for(int j=0;j<n;j++)
if(tren(j,u)+tren(j,v)==1)
{
if(kt==0)
{
ktr[par_id[j]]=(tmp[j]<val);
}else
{
ktr[par_id[j]]=(tmp[j]==val);
}
}
}else
{
int kt=0;
for(int j=0;j<n;j++)
if(tren(j,u)+tren(j,v)==1&&ktr[par_id[j]]!=-1)
{
vector<int>luu=lis;
for(int t=0;t<n-1;t++)
if(luu[t]==par_id[j])
luu[t]=i;
if(ktr[par_id[j]]==0)
{
kt=(my_ask(luu)>val);
}else
{
kt=(my_ask(luu)==val);
}
break;
}
for(int j=0;j<n;j++)
if(tren(j,u)+tren(j,v)==1&&ktr[par_id[j]]==-1)
{
vector<int>luu=lis;
for(int t=0;t<n-1;t++)
if(luu[t]==par_id[j])
luu[t]=i;
tmp[j]=my_ask(luu);
if(kt==0)
{
ktr[par_id[j]]=(tmp[j]<val);
}else
{
ktr[par_id[j]]=(tmp[j]==val);
}
}
}
}
}
for(auto i:lis)
if(ktr[i]==-1)
ktr[i]=1;
while(1)
{
int kt=0,sl=0;
for(int i=0;i<m;i++)
if(ktr[i]==-1)
kt=1;
if(kt==0)
break;
for(int i=0;i<m;i++)
if(ktr[i]==1)
sl++;
if(sl==n-1)
break;
T.init();
vector<int>s;
for(int i=0;i<m;i++)
if(ktr[i]==-1&&T.update(canh[i].fs,canh[i].sc))
s.pb(i);
memset(pos,0,sizeof(pos));
for(auto i:s)
pos[i]=1;
solve(s);
}
vector<int>kq;
for(int i=0;i<m;i++)
if(ktr[i]==1)
kq.pb(i);
return kq;
}
#ifdef SKY
int main()
{
freopen("A.inp","r",stdin);
freopen("A.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
int n,m;
cin>>n>>m;
vector<int>u,v;
for(int i=1;i<=m;i++)
{
int x,y;
cin>>x>>y;
u.pb(x);
v.pb(y);
}
for(int i=1;i<n;i++)
{
int u;
cin>>u;
// cout<<u<<endl;
chon[u]=1;
}
vector<int>kq=find_roads(n,u,v);
cout<<"ASK "<<query<<endl;
for(int i=0;i<n-1;i++)cout<<kq[i]<<"\n";
return 0;
}
#endif
Compilation message
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from simurgh.cpp:1:
simurgh.cpp: In function 'int my_ask(std::vector<int>)':
simurgh.cpp:64:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
64 | assert(r.size()==n-1);
| ~~~~~~~~^~~~~
simurgh.cpp: In function 'void solve(std::vector<int>)':
simurgh.cpp:125:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
125 | if(val+s.size()==my_ans)
| ~~~~~~~~~~~~^~~~~~~~
simurgh.cpp:137:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
137 | for(int i=0;i<s.size();i++)
| ~^~~~~~~~~
simurgh.cpp:138:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
138 | if(i*2<s.size())
| ~~~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
4564 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
4564 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
4564 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1236 KB |
correct |
| 2 |
Runtime error |
3 ms |
4564 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
4564 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
