답안 #102714

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
102714 2019-03-27T08:10:37 Z bert30702 통행료 (IOI18_highway) C++17
컴파일 오류
0 ms 0 KB
#include <bits/stdc++.h>
#include "highway.h"
#define pii pair<int, int>
#define F first
#define S second
#define int long long
using namespace std;
const int MX = 1e6 + 100;
vector<pii> G1[MX], G2[MX];
bitset<MX> pass, edge;
int deep[MX];
//void answer(int a, int b) {
//	cout << "! " << a << ' ' << b;
//}
//int ask(vector<int32_t> v) {
//	for(auto it: v) cout << it << ' '; cout << endl;
//	int val; cin >> val; return val;
//}
vector<pii> que;
void dfs(int u, int l, int d) {
	que.push_back({u, l});
	deep[u] = d;
	for(auto it: G2[u]) {
		dfs(it.F, it.S, d + 1);
	}
}
void find_pair(int32_t n, vector<int32_t> u, vector<int32_t> v, int a, int b) {
	for(int i = 0; i < u.size(); i ++) {
		G1[u[i]].push_back({v[i], i});
		G1[v[i]].push_back({u[i], i});
	}
	int d = ask(vector<int32_t>(u.size(), 0)) / a;
	int l = 0, r = u.size() - 1;
	while(l != r) {
		int m = l + r >> 1;
		vector<int32_t> query(u.size(), 0);
		for(int j = l; j <= m; j ++) query[j] = 1;
		if(ask(query) > d * a) r = m;
		else                   l = m + 1;
	}
	pass[u[l]] = pass[v[l]] = edge[l] = true;
	queue<pii> q;
	q.push({u[l], l});
	q.push({v[l], l});
	while(q.size()) {
		pii p = q.front(); q.pop();
		for(auto i: G1[p.F]) {
			if(!pass[i.F]) {
				edge[i.S] = true;
				pass[i.F] = true;
				G2[p.F].push_back(i);
				q.push(i);
			}
		}
	}
	int x = -1, y = -1;
	{
		que.clear();
		dfs(u[l], l, 1);
		sort(que.begin(), que.end(), [](pii a, pii b) {
			return deep[a.F] < deep[b.F];	
		});
		int l = 0, r = que.size() - 1;
		while(l != r) {
			int m = l + r >> 1;
			vector<int32_t> query(u.size(), 1);
			for(int i = 0; i < u.size(); i ++) {
				if(edge[i]) query[i] = 0;
			}
			for(int i = m + 1; i <= r; i ++) {
				query[que[i].S] = 1;
			}
			if(ask(query) > d * a) l = m + 1;
			else                   r = m;
		}
		x = que[l].F;
	}
	{
		que.clear();
		dfs(v[l], l, 1);
		sort(que.begin(), que.end(), [](pii a, pii b) {
			return deep[a.F] < deep[b.F];
		});
		int l = 0, r = que.size() - 1;
		while(l != r) {
			int m = l + r >> 1;
			vector<int32_t> query(u.size(), 1);
			for(int i = 0; i < u.size(); i ++) {
				if(edge[i]) query[i] = 0;
			}
			for(int i = m + 1; i <= r; i ++) {
				query[que[i].S] = 1;
			}
			if(ask(query) > d * a) l = m + 1;
			else                   r = m;
		}
		y = que[l].F;
	}
	answer(x, y);
}
//main () {
//	find_pair(4, {0, 0, 0, 1, 1, 2}, {1, 2, 3, 2, 3, 3}, 1, 2);
//}

Compilation message

highway.cpp: In function 'void find_pair(int32_t, std::vector<int>, std::vector<int>, long long int, long long int)':
highway.cpp:28:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < u.size(); i ++) {
                 ~~^~~~~~~~~~
highway.cpp:35:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = l + r >> 1;
           ~~^~~
highway.cpp:65:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    int m = l + r >> 1;
            ~~^~~
highway.cpp:67:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0; i < u.size(); i ++) {
                   ~~^~~~~~~~~~
highway.cpp:86:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    int m = l + r >> 1;
            ~~^~~
highway.cpp:88:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0; i < u.size(); i ++) {
                   ~~^~~~~~~~~~
/tmp/ccJV6mV5.o: In function `main':
grader.cpp:(.text.startup+0x125): undefined reference to `find_pair(int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, int, int)'
collect2: error: ld returned 1 exit status