제출 #423311

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
423311		Rudy420	Simurgh (IOI17_simurgh)	C++17	13 / 100	136 ms	14412 KiB

simurgh

#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define lg length()
#define INF 2000000005
#define LINF 1000000000000000005
#define all(x) (x).begin(), (x).end()
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l,int r){return uniform_int_distribution<int>(l,r)(rng);}
#include "simurgh.h"

const pii nul = {-1, -1};
int n,m;
vector<vector<pii>> g,G;
vector<int> f,h,act,hg,w,vz,p,inans;
vector<pii> pr,sb;
set <int> t,b;

void DFS(int nod){
	act[nod] = 1;
	for(pii i : g[nod]){
		if(hg[i.x]){
			if(i.x != pr[nod].x && (sb[nod].x == -1 || hg[i.x] < hg[sb[nod].x])){
				sb[nod] = i;
				for(pii j : g[i.x]){
					if(act[j.x] && pr[j.x].x == i.x){
						h[i.y] = j.y;
					}
				}
			}
			continue;
		}
		hg[i.x] = hg[nod] + 1;
		pr[i.x] = make_pair(nod, i.y);
		t.insert(i.y);
		DFS(i.x);
		if(sb[i.x].x != -1 && hg[sb[i.x].x] <= hg[nod]) f[i.y] = sb[i.x].y; 

		if(sb[i.x].x != -1 && (sb[nod].x == -1 || hg[sb[i.x].x] < hg[sb[nod].x])){
			sb[nod] = sb[i.x];
		}
	}
	if(sb[nod].x != -1) b.insert(sb[nod].y);
	act[nod] = 0;
}

void DFS2(int nod){
	vz[nod] = 1;
	for(pii i : G[nod]){
		if(vz[i.x]) continue;
		w[i.x] = w[nod] - i.y;
		DFS2(i.x);
	}
}

int Par(int nod){
    if(p[p[nod]] == p[nod]) return p[nod];
    else return p[nod] = Par(p[nod]);
}

void Unite(int x, int y){
    x = Par(x); y = Par(y);
    if(x == y) return;
    if(rand(0,1)%2) swap(x,y);
    p[y] = x;
}

int Ask(int nod, int l, int r, vector<int> &u, vector<int> &v){
	vector<int> qry;
	int c = 0;
	for(int j=0;j<n;j++) p[j] = j;
	for(int j=l;j<=r;j++){
		qry.push_back(g[nod][j].y);
		Unite(nod, g[nod][j].x);
		c += inans[g[nod][j].y];
	}
	for(int i : t){
		if(Par(u[i]) != Par(v[i])){
			Unite(u[i], v[i]);
			qry.push_back(i);
			c += w[i];
		}
	}
	return count_common_roads(qry) - c;
}

vector<int> find_roads(int N, vector<int> u, vector<int> v) {
	vector <int> ans;
	n = N; m = sz(u);
	for(int i=0;i<n;i++) g.push_back({});
	for(int i=0;i<m;i++){
		g[u[i]].push_back({v[i],i});
		g[v[i]].push_back({u[i],i});
	}

	f.resize(m,-1);
	h.resize(m,-1);
	hg.resize(n,0);
	sb.resize(n,nul);
	pr.resize(n,nul);
	act.resize(n,0);
	w.resize(m,-1);
	vz.resize(m,0);

	hg[0] = 1;
	DFS(0);

	//for(int i : t) cout << i << ',' << f[i] << '\n';
	//cout << '\n';
	//for(int i : b) cout << i << ',' << h[i] << '\n';

	for(int i=0;i<m;i++) G.push_back({});
	vector <int> qry;
	for(int i : t) qry.push_back(i);
	int C = count_common_roads(qry);
	for(int i : t){
		if(f[i] == -1) continue;
		qry.erase(find(all(qry),i));
		qry.push_back(f[i]);
		int c = count_common_roads(qry);
		qry.pop_back();
		qry.push_back(i);
		G[i].push_back({f[i],C-c});
		G[f[i]].push_back({i,c-C});
		if(C-c) w[i] = (C-c+1)/2;
	}
	for(int i : b){
		qry.erase(find(all(qry),h[i]));
		qry.push_back(i);
		int c = count_common_roads(qry);
		qry.pop_back();
		qry.push_back(h[i]);
		G[i].push_back({h[i],c-C});
		G[h[i]].push_back({i,C-c});
		if(C-c) w[h[i]] = (C-c+1)/2;
	}

	for(int i : t){
		if(!vz[i] && w[i]!=-1) DFS2(i);
	}
	for(int i : t){
		if(f[i] == -1) w[i] = 1;
	}

	inans.resize(m, 0);
	p.resize(n);
	vector<int> d(n,0);
	queue <int> q;
	for(int i=0;i<n;i++){
		d[i] = Ask(i, 0, sz(g[i]) - 1, u, v);
		if(d[i] == 1) q.push(i);
	}

	for(int i=1;i<n;i++){
		int t = q.front();
		q.pop();
		int l=0,r=sz(g[t])-1;
		while(l!=r){
			int mid = (l+r)/2;
			if(Ask(t, l, mid, u, v)) r = mid;
			else l = mid + 1;
		}
		ans.push_back(g[t][l].y);
		inans[g[t][l].y] = 1;
		int p = g[t][l].x;
		d[p]--;
		if(d[p] == 1) q.push(p);
	}


	return ans;

}

• Subtask 1: 13 / 13
• Subtask 2: 0 / 17
• Subtask 3: 0 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 30