oj.uz

답안 #778079

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
778079 2023-07-10T05:57:31 Z CSQ31 Simurgh (IOI17_simurgh) C++17
13 / 100
 3000 ms 11980 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 = 1;
int ask(){
	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';
	int cnt = m;
	for(int i=0;i<m;i++){
		//cout<<good[i]<<" ";
		if(good[i]>=0){
			cnt--;
			solved.pb(i);
		}
	}
	//cout<<'\n';
	edges.clear();
	while(cnt){
		init(n);
		e.clear();
		for(int i=0;i<m;i++){
			if(good[i] >= 0)continue;
			if(unite(v[i],u[i]))e.pb(i);
		}
		cnt-=sz(e);
		solve(0,sz(e)-1,n);
		for(int x:e)solved.pb(x);
	}
	vector<int>ans;
	for(int i=0;i<m;i++){
		if(good[i] == 1)ans.pb(i);
	}
	return ans;
}

Subtask #1
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4948 KB correct
2 Correct 2 ms 4948 KB correct
3 Correct 2 ms 4948 KB correct
4 Correct 2 ms 5016 KB correct
5 Correct 2 ms 4948 KB correct
6 Correct 2 ms 5016 KB correct
7 Correct 2 ms 4948 KB correct
8 Correct 2 ms 4948 KB correct
9 Correct 3 ms 4948 KB correct
10 Correct 3 ms 4948 KB correct
11 Correct 3 ms 4948 KB correct
12 Correct 2 ms 4948 KB correct
13 Correct 3 ms 5048 KB correct

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4948 KB correct
2 Correct 2 ms 4948 KB correct
3 Correct 2 ms 4948 KB correct
4 Correct 2 ms 5016 KB correct
5 Correct 2 ms 4948 KB correct
6 Correct 2 ms 5016 KB correct
7 Correct 2 ms 4948 KB correct
8 Correct 2 ms 4948 KB correct
9 Correct 3 ms 4948 KB correct
10 Correct 3 ms 4948 KB correct
11 Correct 3 ms 4948 KB correct
12 Correct 2 ms 4948 KB correct
13 Correct 3 ms 5048 KB correct
14 Correct 7 ms 5148 KB correct
15 Correct 6 ms 5144 KB correct
16 Correct 6 ms 5076 KB correct
17 Correct 7 ms 5020 KB correct
18 Correct 3 ms 5012 KB correct
19 Correct 5 ms 5076 KB correct
20 Correct 5 ms 5076 KB correct
21 Correct 5 ms 5076 KB correct
22 Incorrect 3 ms 5076 KB WA in grader: NO
23 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4948 KB correct
2 Correct 2 ms 4948 KB correct
3 Correct 2 ms 4948 KB correct
4 Correct 2 ms 5016 KB correct
5 Correct 2 ms 4948 KB correct
6 Correct 2 ms 5016 KB correct
7 Correct 2 ms 4948 KB correct
8 Correct 2 ms 4948 KB correct
9 Correct 3 ms 4948 KB correct
10 Correct 3 ms 4948 KB correct
11 Correct 3 ms 4948 KB correct
12 Correct 2 ms 4948 KB correct
13 Correct 3 ms 5048 KB correct
14 Correct 7 ms 5148 KB correct
15 Correct 6 ms 5144 KB correct
16 Correct 6 ms 5076 KB correct
17 Correct 7 ms 5020 KB correct
18 Correct 3 ms 5012 KB correct
19 Correct 5 ms 5076 KB correct
20 Correct 5 ms 5076 KB correct
21 Correct 5 ms 5076 KB correct
22 Incorrect 3 ms 5076 KB WA in grader: NO
23 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4948 KB correct
2 Correct 3 ms 4948 KB correct
3 Correct 1795 ms 10092 KB correct
4 Execution timed out 3048 ms 11980 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4948 KB correct
2 Correct 2 ms 4948 KB correct
3 Correct 2 ms 4948 KB correct
4 Correct 2 ms 5016 KB correct
5 Correct 2 ms 4948 KB correct
6 Correct 2 ms 5016 KB correct
7 Correct 2 ms 4948 KB correct
8 Correct 2 ms 4948 KB correct
9 Correct 3 ms 4948 KB correct
10 Correct 3 ms 4948 KB correct
11 Correct 3 ms 4948 KB correct
12 Correct 2 ms 4948 KB correct
13 Correct 3 ms 5048 KB correct
14 Correct 7 ms 5148 KB correct
15 Correct 6 ms 5144 KB correct
16 Correct 6 ms 5076 KB correct
17 Correct 7 ms 5020 KB correct
18 Correct 3 ms 5012 KB correct
19 Correct 5 ms 5076 KB correct
20 Correct 5 ms 5076 KB correct
21 Correct 5 ms 5076 KB correct
22 Incorrect 3 ms 5076 KB WA in grader: NO
23 Halted 0 ms 0 KB -