Submission #133880

#	Time	Username	Problem	Language	Result	Execution time	Memory
133880		nvmdava	Simurgh (IOI17_simurgh)	C++17	0 / 100	1929 ms	4972 KiB

simurgh

#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<pair<int, int> > edge;
int n, m;
bool ans[150000];
bool ch[150000];

int p[505];
int get(int v, int i){
	return edge[i].ff + edge[i].ss - v;
}

void reset(){
	for(int i = 0; i < n; i++)
		p[i] = i;
}

int find(int v){
	return v == p[v] ? v : p[v] = find(p[v]);
}

bool merge(int v, int u){
	v = find(v);
	u = find(u);
	if(v == u) return 0;
	p[v] = u;
	return 1;
}

vector<int> inq;
vector<int> tree;
int t;
int ask(){
	reset();
	for(int& x : inq)
		merge(edge[x].ff, edge[x].ss);
	t = 0;
	for(int& x : tree){
		if(merge(edge[x].ff, edge[x].ss)){
			inq.push_back(x);
			t += ans[x];
		}
	}
	return count_common_roads(inq);
}

int par[505];
int dep[505];
vector<int> adj[505];

void dfs(int v){
	for(int& x : adj[v]){
		int u = get(v, x);
		if(dep[u]) continue;
		par[u] = x;
		dep[u] = dep[v] + 1;
		tree.push_back(x);
		dfs(u);
	}
}

vector<int> cyc, fin, onn, off;
int fillexc(int x){
	inq = cyc;
	for(int& a : inq){
		if(a == x){
			swap(a, inq.back());
			inq.pop_back();
			break;
		}
	}
	return ask();
}
vector<int> vall;
void solvecycle(){
	if(fin.empty()) return;
	if(onn.empty() && off.empty()){
		fin.push_back(cyc[0]);
		int lo = -1;
		for(int& x : cyc)
			vall.push_back(fillexc(x));
		for(int& x : vall)
			lo = max(lo, x);
		for(int i = cyc.size() - 1; i >= 0; i--){
			ch[cyc[i]] = 1;
			ans[cyc[i]] = vall[i] - lo;
		}
	} else {
		int lo;
		if(off.empty())
			lo = fillexc(onn[0]);
		else 
			lo = fillexc(off[0]) - 1;
		for(int& x : fin){
			ch[x] = 1;
			ans[x] = (fillexc(x) == lo);
		}
	}
}

void solvetree(){
	for(int i = 0; i < m; i++){
		if(dep[edge[i].ff] < dep[edge[i].ss]) swap(edge[i].ff, edge[i].ss);
		if(dep[edge[i].ff] - dep[edge[i].ss] == 1) continue;
		cyc.clear(); fin.clear(); off.clear(); onn.clear();
		cyc.push_back(i);
		int s = edge[i].ff;
		while(s != edge[i].ss){
			cyc.push_back(par[s]);
			if(ch[par[s]] == 0) fin.push_back(par[s]);
			else if(ans[par[s]] == 1) onn.push_back(par[s]);
			else off.push_back(par[s]);
			s = get(s, par[s]);
		}
		solvecycle();
	}
	for(int& x : tree){
		if(ch[x] == 0){
			ch[x] = ans[x] = 1;
		}
	}
}

vector<int> imsad;
bool in[505];

void dfs2(int v){
	in[v] = 1;
	for(int i = adj[v].size() - 1; i >= 0; i--){
		if(ch[adj[v][i]]){
			swap(adj[v][i], adj[v].back());
			adj[v].pop_back();
			continue;
		}
		int u = get(v, adj[v][i]);
		if(in[u]) continue;
		imsad.push_back(adj[v][i]);
		dfs2(u);
	}
}

void solvethisshit(){
	if(imsad.empty()) return;
	inq = imsad;
	if(ask() == t){
		for(int& x : imsad){
			ch[x] = 1;
			ans[x] = 0;
		}
		return;
	}
	int l = 0, r = imsad.size() - 1;
	while(l != r){
		int m = (l + r) >> 1;
		inq.clear();
		for(int i = 0; i <= m; i++)
			inq.push_back(imsad[i]);
		if(ask() == t) l = m + 1;
		else r = m;
	}
	for(int i = 0; i < r; i++){
		ch[imsad[i]] = 1;
		ans[imsad[i]] = 0;
	}
	ch[imsad[r]] = ans[imsad[r]] = 1;
}

vector<int> ACpls;

vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
	::n = n;
	m = u.size();
	for(int i = 0; i < m; i++){
		adj[v[i]].push_back(i);
		adj[u[i]].push_back(i);
		edge.push_back({v[i], u[i]});
	}
	dep[0] = 1;
	dfs(0);
	if(m == n - 1){
		return tree; 
	}
	solvetree();
	do{
		memset(in, 0, sizeof in);
		imsad.clear();
		for(int i = 0; i < n; i++){
			if(in[i]) continue;
			dfs2(i);
		}
		solvethisshit();
	} while(!imsad.empty());
	for(int i = 0; i < m; i++){
		if(ans[i]) ACpls.push_back(i);
	}
	return ACpls;
}

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