oj.uz

Submission #797530

# Submission time Handle Problem Language Result Execution time Memory
797530 2023-07-29T14:51:48 Z alvingogo Simurgh (IOI17_simurgh) C++14
0 / 100
 2 ms 300 KB 
#include "simurgh.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;

struct DSU{
	vector<int> bo;
	void init(int x){
		bo.resize(x);
		iota(bo.begin(),bo.end(),0);
	}
	int find(int x){
		return bo[x]==x?x:bo[x]=find(bo[x]);
	}
	int merge(int x,int y){
		x=find(x);
		y=find(y);
		if(x==y){
			return 0;
		}
		bo[x]=y;
		return 1;
	}
}dsu;

int query(const vector<int>& r){
	return count_common_roads(r);
}
vector<int> ans,vis;
vector<vector<pair<int,int> > > e;
struct TR{
	struct no{
		vector<pair<int,int> > ch;
		vector<int> sub;
	};
	vector<int> s;
	int pas;
	vector<no> v;
	int n;
	void init(int x){
		n=x;
		v.resize(n);
		for(int i=0;i<n;i++){
			v[i].sub.resize(n);
		}
	}
	void add(int x,int y,int t){
		v[x].ch.push_back({y,t});
		v[y].ch.push_back({x,t});
		s.push_back(t);
	}
	void dfs(int r,int f,int k){
		v[r].sub[r]=1;
		for(auto h:v[r].ch){
			if(h.fs!=f){
				dfs(h.fs,r,h.sc);
				for(int i=0;i<n;i++){
					v[r].sub[i]|=v[h.fs].sub[i];
				}
			}
		}
		if(r==f){
			return;
		}
		int val=-1;
		vector<int> ud;
		vector<int> l;
		for(int i=0;i<n;i++){
			if(v[r].sub[i]){
				for(auto h:e[i]){
					if(v[r].sub[h.fs]){
						continue;
					}
					if(vis[h.sc]){
						l.push_back(h.sc);
					}
					else{
						vis[h.sc]=1;
						auto z=s;
						for(auto &e:z){
							if(e==k){
								e=h.sc;
							}
						}
						int u=query(z)-pas;
						if(u==1){
							if(val==-1){
								val=0;
								for(auto e:ud){
									ans[e]=0;
								}
								ud.clear();
							}
							ans[h.sc]=1;
						}
						else if(u==-1){
							if(val==-1){
								val=1;
								for(auto e:ud){
									ans[e]=1;
								}
								ud.clear();
							}
							ans[h.sc]=0;
						}
						else{
							ud.push_back(h.sc);
						}
					}
				}
			}
		}
		if(val==-1){
			if(l.size()){
				auto h=l[0];
				auto z=s;
				for(auto &e:z){
					if(e==k){
						e=h;
					}
				}
				int u=query(z)-pas;
				if(u==0){
					val=ans[h];
				}
				else{
					val=1-ans[h];
				}
			}
			else{
				val=1;
			}
			for(auto h:ud){
				ans[h]=val;
			}
		}
		ans[k]=val;
	}
}tr;
vector<int> find_roads(int n, vector<int> u, vector<int> v) {
	int m=u.size();
	ans.resize(m);
	vis.resize(m);
	dsu.init(n);
	tr.init(n);
	e.resize(n);
	for(int i=0;i<m;i++){
		if(dsu.merge(u[i],v[i])){
			tr.add(u[i],v[i],i);
		}
		else{
			e[u[i]].push_back({v[i],i});
			e[v[i]].push_back({u[i],i});
		}
	}
	tr.pas=query(tr.s);
	tr.dfs(0,0,-1);
	vector<int> ret;
	for(int i=0;i<m;i++){
		if(ans[i]){
			ret.push_back(i);
		}
	}
	return ret;
}

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 212 KB correct
2 Incorrect 1 ms 212 KB WA in grader: NO
3 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 212 KB correct
2 Incorrect 1 ms 212 KB WA in grader: NO
3 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 212 KB correct
2 Incorrect 1 ms 212 KB WA in grader: NO
3 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB correct
2 Incorrect 1 ms 300 KB WA in grader: NO
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 212 KB correct
2 Incorrect 1 ms 212 KB WA in grader: NO
3 Halted 0 ms 0 KB -