oj.uz

답안 #135018

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
135018 2019-07-23T14:25:41 Z nvmdava Simurgh (IOI17_simurgh) C++17
0 / 100
 2 ms 376 KB 
#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
#define vi vector<int>

vector<pair<int, int> > e;
bool ans[150000], ch[150000], in[505];
vi inq, tr, adj[505], vall, qq, ret, cyc, fin, onn, off;

int p[505], t, par[505], d[505], n, m;

int get(int v, int i){
	return e[i].ff + e[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;
}

int ask(){
	reset();
	for(int x : inq)
		merge(e[x].ff, e[x].ss);
	t = 0;
	for(int x : tr){
		if(merge(e[x].ff, e[x].ss)){
			inq.pb(x);
			t += ans[x];
		}
	}
	return count_common_roads(inq);
}

void dfs(int v){
	for(int x : adj[v]){
		int u = get(v, x);
		if(d[u]) continue;
		par[u] = x;
		d[u] = d[v] + 1;
		tr.pb(x);
		dfs(u);
	}
}

int fexc(int x){
	inq = cyc;
	for(int a : inq){
		if(a == x){
			swap(a, inq.back());
			inq.pop_back();
			break;
		}
	}
	return ask();
}

void cycle(){
	if(fin.empty()) return;
   int lo;
	if(onn.empty() && off.empty()){
		lo = -1;
		vall.clear();
		for(int x : cyc)
			vall.pb(fexc(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]] = (lo - vall[i]);
		}
	} else {
		if(off.empty())
			lo = fexc(onn[0]);
		else
			lo = fexc(off[0]) - 1;
		for(int x : fin){
			ch[x] = 1;
			ans[x] = (fexc(x) == lo);
		}
	}
}

void tree(){
	for(int i = 0; i < m; i++){
		if(d[e[i].ff] < d[e[i].ss]) swap(e[i].ff, e[i].ss);
		if(d[e[i].ff] - d[e[i].ss] == 1) continue;
		cyc.clear(); fin.clear(); off.clear(); onn.clear();
		cyc.pb(i);
		int s = e[i].ff;
		while(s != e[i].ss){
			cyc.pb(par[s]);
			if(ch[par[s]] == 0) fin.pb(par[s]);
			else if(ans[par[s]] == 1) onn.pb(par[s]);
			else off.pb(par[s]);
			s = get(s, par[s]);
		}
		cycle();
	}
	for(int x : tr){
		if(ch[x] == 0){
			ch[x] = ans[x] = 1;
		}
	}
}

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;
		qq.pb(adj[v][i]);
		dfs2(u);
	}
}

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


vi find_roads(int N, vi u, vi v) {
	n = N;
	m = u.size();
	for(int i = 0; i < m; i++){
		adj[v[i]].pb(i);
		adj[u[i]].pb(i);
		e.pb({v[i], u[i]});
	}
	d[0] = 1;
	dfs(0);
	tree();
	do{
		memset(in, 0, sizeof in);
		qq.clear();
		for(int i = 0; i < n; i++)
			if(!in[i])
            dfs2(i);
		vsolve();
	} while(!qq.empty());
	for(int i = 0; i < m; i++)
		if(ans[i]) ret.pb(i);
	return ret;
}

Subtask #1
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB WA in grader: NO
2 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB WA in grader: NO
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB WA in grader: NO
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB correct
2 Incorrect 2 ms 376 KB WA in grader: NO
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB WA in grader: NO
2 Halted 0 ms 0 KB -