| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 778347 |
2023-07-10T08:45:58 Z |
CSQ31 |
Simurgh (IOI17_simurgh) |
C++17 |
|
3 ms |
4948 KB |
#include "simurgh.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define sz(a) (int)(a.size())
#define all(a) a.begin(),a.end()
typedef long long int ll;
typedef pair<int,int> pii;
const int MAXN = 2e5;
int par[MAXN],szz[MAXN],good[MAXN],tree[MAXN];
vector<pii>adj[MAXN],ed;
int find(int x){
if(x==par[x])return x;
return par[x] = find(par[x]);
}
bool unite(int a,int b){
a = find(a);
b = find(b);
if(a==b)return 0;
if(szz[a] > szz[b])swap(a,b);
par[a] = b;
szz[b]+=szz[a];
return 1;
}
void init(int n){
for(int i=0;i<n;i++){
par[i] = i;
szz[i] = 1;
}
}
set<int>edges;
vector<int>edge;
int Q = 0;
int ask(){
Q++;
assert(Q<=9000);
vector<int>r;
if(edges.empty())for(int x:edge)r.pb(x);
else for(int x:edges)r.pb(x);
//assert(sz(r)==nn-1);
return count_common_roads(r);
}
pii p[MAXN];
int dep[MAXN],vis[MAXN],glob;
void dfs(int v,int u){
vis[v] = 1;
for(pii z:adj[v]){
int x = z.fi;
int id = z.se;
if(vis[x] || x==u)continue;
tree[id] = 1;
edges.insert(id);
dep[x] = dep[v]+1;
p[x] = {v,id};
dfs(x,v);
}
}
void dfs2(int v,int u){
for(pii z:adj[v]){
int x = z.fi;
int id = z.se;
if(tree[id]){
if(x!=u)dfs2(x,v);
continue;
}
if(dep[x] > dep[v])continue; //go downwards
vector<int>path,res;
int cur = v;
while(cur != x){
path.pb(p[cur].se);
cur = p[cur].fi;
}
//for(int e:path)cout<<e<<" ";
//cout<<'\n';
int have = 0;
for(int e:path)have += (good[e] == -1);
if(!have)continue; //if all tree edge part of this cycle is known,skip
edges.insert(id);
if(have == sz(path)){ //everything is unknown
//cout<<"case 1"<<'\n';
for(int e:path){
edges.erase(e);
res.pb(ask());
edges.insert(e);
}
path.pb(id);
res.pb(glob);
int s = sz(path);
for(int i=0;i<s;i++){
int j = (i+s-1) % s;
if(res[i] == res[j])continue;
good[path[i]] = 1;
good[path[j]] = 0;
if(res[i] > res[j])swap(good[path[i]],good[path[j]]);
}
for(int i=0;i<s;i++){
int j = (i+s-1) % s;
if(good[path[j]] >= 0 && res[i] == res[j])good[path[i]] = good[path[j]];
}
for(int i=s-1;i>=0;i--){
int j = (i+1) % s;
if(good[path[j]] >= 0 && res[i] == res[j])good[path[i]] = good[path[j]];
}
for(int x:path){
if(good[x] == -1)good[x] = 0;
}
}else{
//cout<<"case 2"<<'\n';
if(good[id] == -1){
for(int e:path){
if(good[e] == -1)continue;
edges.erase(e);
int res2 = ask();
edges.insert(e);
if(res2 == glob)good[id] = good[e];
else if(res2 > glob)good[id] = 1;
else good[id] = 0;
break;
}
}
//cout<<good[id]<<'\n';
for(int e:path){
if(good[e] != -1)continue;
edges.erase(e);
int res2 = ask();
edges.insert(e);
if(res2 == glob)good[e] = good[id];
else if(res2 > glob)good[e] = 0;
else good[e] = 1;
}
}
edges.erase(id);
}
}
vector<int>e,solved;
int make(){
int cnt = 0;
for(int x:solved){
if(unite(ed[x].fi,ed[x].se)){
edge.pb(x);
cnt+=good[x];
}
}
return cnt;
}
void solve(vector<int>e,int n,int num){
if(n==1){
good[e[0]] = 1;
return;
}
int m = sz(e);
if(m==1)return;
vector<int>l,r;
for(int i=0;i<m/2;i++)l.pb(e[i]);
edge.clear();
for(int x:l){
if(unite(ed[x].fi,ed[x].se))edge.pb(x);
}
int tot = make();
int res = ask();
for(int i=m/2;i<m;i++)r.pb(e[i]);
int x = res-tot;
if(x)solve(l,n,x);
if(num-x)solve(r,n,num-x);
}
mt19937 seed(chrono::high_resolution_clock::now().time_since_epoch().count());
vector<int> find_roads(int N,vector<int> u,vector<int> v) {
int n = N;
int m = sz(u);
for(int i=0;i<m;i++)ed.pb({v[i],u[i]});
for(int i=0;i<m;i++){
good[i] = -1;
adj[u[i]].pb({v[i],i});
adj[v[i]].pb({u[i],i});
}
dfs(0,-1);
glob = ask();
dfs2(0,-1);
assert(Q<=1000);
for(int x:edges){
if(good[x]==-1)good[x] = 1; //this is a bridge
}
for(int x:edges)solved.pb(x);
edges.clear();
for(int i=0;i<n;i++){
e.clear();
for(pii x:adj[i]){
if(x.fi > i)e.pb(x.se);
}
if(e.empty())continue;
edge.clear();
for(int x:e){
unite(v[x],u[x]);
edge.pb(x);
}
int tot = make();
int res = ask();
if(res-tot)solve(e,n,res-tot);
}
vector<int>ans;
for(int i=0;i<m;i++){
if(good[i] == 1)ans.pb(i);
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4948 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4948 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4948 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4948 KB |
correct |
| 2 |
Incorrect |
3 ms |
4948 KB |
WA in grader: NO |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4948 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
