제출 #415720

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
415720		_fractal	통행료 (IOI18_highway)	C++14	51 / 100	310 ms	12816 KiB

highway

#include "highway.h"
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

vector<vector<pair<int, int>>> g;
vector<int> lmao;
long long cur;
int M;

int calc(int v, vector<pair<int, int>> t) {
	int tl = 1, tr = t.size() - 1, ans = v;
	vector<int> get(M, 0);
	for (auto &i : get) i = 0;
	for (int i = 1; i < t.size(); ++i)
		get[lmao[t[i].second]] = 1;
	if (ask(get) == cur)
		return v;
	while (tl <= tr) {
		int tm = tl + tr >> 1;
		for (auto &i : get) i = 0;
		for (int i = 1; i < t.size(); ++i)
			get[lmao[t[i].second]] = 1;
		for (int i = 1; i <= tm; ++i)
			get[lmao[t[i].second]] = 0;
		if (ask(get) == cur) {
			ans = t[tm].second;
			tr = tm - 1;
		}
		else {
			tl = tm + 1;
		}
	}	
	return ans;
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
	M = U.size();
	vector<int> activ;
	vector<int> get(M, 0);
	vector<int> was(N, 0);
	g = vector<vector<pair<int, int>>> (N, vector<pair<int, int>>(0));
	cur = ask(get);
	lmao = vector<int>(N, 0);
	for (int i = 0; i < M; ++i) {
		g[V[i]].push_back({U[i], i});
		g[U[i]].push_back({V[i], i});
	}
	int tl = 0, tr = M, ans = -1;
	while (tl <= tr) {
		int tm = tl + tr >> 1;
		for (int i = 0; i < M; ++i)
			get[i] = (i <= tm ? 0 : 1);
		if (ask(get) == cur) {
			ans = tm;
			tr = tm - 1;
		}
		else {
			tl = tm + 1;
		}
	}
	queue<int> q;
	vector<int> d(N, -1), col(N, 0);
	vector<pair<int, int>> is[2];
	q.push(U[ans]), q.push(V[ans]);
	d[U[ans]] = d[V[ans]] = 0;
	col[U[ans]] = 0;
	col[V[ans]] = 1;
	while (q.size()) {
		int v = q.front();
		q.pop();
		is[col[v]].push_back({d[v], v});
		for (auto it : g[v]) {
			int to = it.first, c = it.second;
			if (d[to] == -1) {
				d[to] = d[v] + 1;
				col[to] = col[v];
				lmao[to] = c;
				q.push(to);
			}
		}
	}
	sort(is[0].begin(), is[0].end());
	sort(is[1].begin(), is[1].end());
	int a = calc(U[ans], is[0]);
	int b = calc(V[ans], is[1]);
	answer(a, b);
	return;
}

컴파일 시 표준 에러 (stderr) 메시지

highway.cpp: In function 'int calc(int, std::vector<std::pair<int, int> >)':
highway.cpp:16:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |  for (int i = 1; i < t.size(); ++i)
      |                  ~~^~~~~~~~~~
highway.cpp:21:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   21 |   int tm = tl + tr >> 1;
      |            ~~~^~~~
highway.cpp:23:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |   for (int i = 1; i < t.size(); ++i)
      |                   ~~^~~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:52:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |   int tm = tl + tr >> 1;
      |            ~~~^~~~

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