제출 #1063977

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1063977		Tob	통행료 (IOI18_highway)	C++14	0 / 100	11 ms	4184 KiB

highway

#include <bits/stdc++.h>

#include "highway.h"

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;

const int maxN = 90007;

ll odis;
int bio[maxN], dub[maxN], col[maxN];
vector <pii> adj[maxN];

void dfs(int x) {
	bio[x] = 1;
	for (auto y : adj[x]) {
		if (bio[y.F]) continue;
		dub[y.F] = dub[x]+1;
		dfs(y.F);
	}
}

void find_pair(int n, vector <int> u, vector <int> v, int a, int b) {
	int m = u.size();
	vector <int> tmp(m, 0);
	odis = ask(tmp);
	for (int i = 0; i < m; i++) {
		adj[u[i]].pb({v[i], i});
		adj[v[i]].pb({u[i], i});
	}
	dfs(0);
	
	vector <int> e;
	for (int i = 0; i < m; i++) e.pb(i);
	
	sort(all(e), [&](int x, int y) {return max(dub[u[x]], dub[v[x]]) > max(dub[u[y]], dub[v[y]]);});
	int lo = 0, hi = m-1;
	while (lo < hi) {
		int mid = (lo + hi) / 2;
		vector <int> ed(m, 0);
		for (int i = 0; i <= mid; i++) ed[e[i]] = 1;
		if (odis != ask(ed)) hi = mid;
		else lo = mid+1;
	}
	
	int nx = u[e[lo]], ny = v[e[lo]];
	
	queue <int> q;
	memset(bio, -1, sizeof bio);
	bio[nx] = 0; bio[ny] = 0; col[ny] = 1;
	q.push(nx); q.push(ny);
	vector <pii> dod[2];
	dod[0].pb({nx, e[lo]});
	dod[1].pb({ny, e[lo]});
	
	while (!q.empty()) {
		int x = q.front(); q.pop();
		for (auto y : adj[x]) {
			if (bio[y.F] != -1) continue;
			bio[y.F] = bio[x] + 1;
			dod[col[x]].pb(y);
			col[y.F] = col[x];
			q.push(y.F);
		}
	}
	
	sort(all(e), [&](int x, int y){return max(bio[v[x]], bio[u[x]]) < max(bio[v[y]], bio[u[y]]);});
	auto check = [&](int o) {
		lo = 0, hi = dod[o].size()-1;
		while (lo < hi) {
			int mid = (lo + hi) / 2;
			vector <int> ed(m, 0);
			for (int i = 0; i <= mid; i++) ed[dod[o][i].S] = 1;
			for (auto x : dod[o^1]) if (bio[x.F] <= bio[dod[o][mid].F]) ed[x.S] = 1;
			if (odis/a*b != ask(ed)) lo = mid+1;
			else hi = mid;
		}
		return dod[o][lo].F;
	};
	
	int x = check(0), y = check(1);
	answer(x, y);
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 6
• Subtask 4: 0 / 33
• Subtask 5: 0 / 18
• Subtask 6: 0 / 31