| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 778089 |
2023-07-10T06:08:35 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 nn;
bool debug = 0;
int Q = 0;
int ask(){
Q++;
assert(Q<=30000);
vector<int>r;
if(edges.empty())for(int x:edge)r.pb(x);
else for(int x:edges)r.pb(x);
if(debug)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]];
}
}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;
void solve(int l,int r,int n){
if(l>r)return;
init(n);
edge.clear();
for(int i=l;i<=r;i++){
if(unite(ed[e[i]].fi,ed[e[i]].se))edge.pb(e[i]);
}
int tot = 0;
for(int i=0;i<sz(ed);i++){
if(good[i]>=0){
if(unite(ed[i].fi,ed[i].se)){
edge.pb(i);
tot+=good[i];
}
}
}
int res = ask();
edge.clear();
if(res == tot){
for(int i=l;i<=r;i++)good[e[i]] = 0;
return;
}else if(res == tot + r-l+1){
for(int i=l;i<=r;i++)good[e[i]] = 1;
return;
}
int mid = (l+r)/2;
solve(l,mid,n);
solve(mid+1,r,n);
}
vector<int> find_roads(int N,vector<int> u,vector<int> v) {
nn = N;
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);
debug = 0;
//for(int i=0;i<m;i++)cout<<good[i]<<" ";
//cout<<'\n';
for(int x:edges){
if(good[x]==-1)good[x] = 1; //this is a bridge
}
int found = 0;
int cnt = m;
for(int i=0;i<m;i++){
//cout<<good[i]<<" ";
if(good[i]>=0){
cnt--;
found+=good[i];
solved.pb(i);
}
}
edges.clear();
for(int i=0;i<m;i++){
if(good[i]>=0)continue;
if(found==n-1)break;
init(n);
edge.clear();
edge.pb(i);
unite(v[i],u[i]);
int tot = 0;
for(int x:solved){
if(unite(v[x],u[x])){
edge.pb(x);
tot++;
}
}
if(ask() == tot)good[i] = 0;
else{
good[i] = 1;
found++;
}
solved.pb(i);
}
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 |
- |
