제출 #769088

#제출 시각아이디문제언어결과실행 시간메모리
769088ono_de206통행료 (IOI18_highway)C++14
0 / 100
8 ms3112 KiB
#include "highway.h"
#include<bits/stdc++.h>
using namespace std;

#define in insert
#define all(x) x.begin(),x.end()
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second

// #define int long long
 
typedef long long ll;
typedef vector<int> vi;
typedef set<int> si;
typedef multiset<int> msi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;

const int mxn = 1e5 + 10;
vector<int> g[mxn];

void find_pair(int n, vector<int> u, vector<int> v, int A, int B) {
	int m = u.size();
	for(int i = 0; i < m; i++) {
		g[u[i]].pb(v[i]);
		g[v[i]].pb(u[i]);
	}
	// long long tot = ask(vector<int>(m));
	// int l = 0, r = m;
	// while(r - l > 1) {
	// 	int mid = (r + l) / 2;
	// 	vector<int> q(m);
	// 	for(int i = 0; i <= mid; i++) {
	// 		q[i] = 1;
	// 	}
	// 	if(ask(q) == tot) l = mid + 1;
	// 	else r = mid;
	// }
	// int x = u[l], y = v[l], ans1, ans2;

	// auto bfs = [&](int st) -> vector<int> {
	// 	vector<int> ret(n, -1);
	// 	ret[st] = 0;
	// 	queue<int> q;
	// 	q.push(st);
	// 	while(q.size()) {
	// 		int x = q.front();
	// 		q.pop();
	// 		for(int y : g[x]) {
	// 			if(ret[y] != -1) continue;
	// 			ret[y] = ret[x] + 1;
	// 			q.push(y);
	// 		}
	// 	}
	// 	return ret;
	// };

	// auto disX = bfs(x);
	// auto disY = bfs(y);

	// cout << x << ' ' << y << '\n';

	// vector<int> edges;
	// for(int i = 0; i < m; i++) {
	// 	if(disX[u[i]] > disX[v[i]]) swap(u[i], v[i]);
	// 	if(disX[u[i]] < disY[u[i]] && disX[v[i]] < disY[v[i]]) edges.pb(i);
	// }
	// sort(all(edges), [&](int id1, int id2) {
	// 	return disX[v[id1]] < disX[v[id2]];
	// });
	// l = -1, r = edges.size();
	// while(r - l > 1) {
	// 	int mid = (l + r) / 2;
	// 	vector<int> q(m);
	// 	for(int i = mid; i < edges.size(); i++) {
	// 		q[edges[i]] = 1;
	// 	}
	// 	if(ask(q) == tot) r = mid;
	// 	else l = mid;
	// }
	// if(l == -1) ans1 = x;
	// else ans1 = v[edges[l]];

	// edges.clear();
	// for(int i = 0; i < m; i++) {
	// 	if(disY[u[i]] > disY[v[i]]) swap(u[i], v[i]);
	// 	if(disY[u[i]] < disX[u[i]] && disY[v[i]] < disX[v[i]]) edges.pb(i);
	// }
	// sort(all(edges), [&](int id1, int id2) {
	// 	return disY[v[id1]] < disY[v[id2]];
	// });
	// l = -1, r = edges.size();
	// while(r - l > 1) {
	// 	int mid = (l + r) / 2;
	// 	vector<int> q(m);
	// 	for(int i = mid; i < edges.size(); i++) {
	// 		q[edges[i]] = 1;
	// 	}
	// 	if(ask(q) == tot) r = mid;
	// 	else l = mid;
	// }
	// if(l == -1) ans2 = y;
	// else ans2 = v[edges[l]];
	// answer(ans1, ans2);
	answer(69, 69);
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...