제출 #1012640

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

highway

#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
const int sz = 100000;
vector<pi>tree[sz+5];
int visited[sz+5];
int dist_a[sz+5],dist_b[sz+5];
int FIND(vector<int>w,vector<int>candidates,int root,int edge){
	memset(visited,0,sizeof(visited));
	for(int x : candidates) visited[x] = 1;
    w=vector<int>(w.size(),1);
    visited[root] = 0;
	queue<int>q; q.push(root);
	vector<pi>v; v.emplace_back(pi(root,edge));
	while(!q.empty()){
		int cur = q.front(); q.pop();
		for(pi p : tree[cur]){
			int nxt = p.first;
			int id = p.second;
			if(visited[nxt]){
				visited[nxt] = 0;
				v.emplace_back(pi(nxt,id));
				q.push(nxt);
			}
		}
	}
	reverse(v.begin(),v.end());
    for(pi p : v) w[p.second]=0;
    ll d = ask(w);
	int l = 0,r = v.size()-1;
	while(l<=r){
		int M = (l+r)>>1;
		for(int i=0; i<=M; i++) w[v[i].second] = 1;
		if(ask(w) > d) r = M-1;
		else l = M+1;
		for(int i=0; i<=M; i++) w[v[i].second] = 0;
	}
	return v[l].first;
}
void find_pair(int n, std::vector<int> U, std::vector<int> V, int A, int B) {
	for(int i=0; i<n; i++){
		tree[i].clear();
		visited[i] = 0;
		dist_a[i] = dist_b[i] = 1e9;
	}
	int m = U.size();
	for(int i=0; i<U.size(); i++){
		int a = U[i],b = V[i];
		tree[a].emplace_back(pi(b,i));
		tree[b].emplace_back(pi(a,i));
	}
	vector<int>w(m,0);
	ll d = ask(w);
	int l = 0,r = m-1;
	while(l<=r){
		int M = (l+r)>>1;
		for(int i=0; i<=M; i++) w[i] = 1;
		if(ask(w) > d) r = M-1;
		else l = M+1;
		for(int i=0; i<=M; i++) w[i] = 0;
	}
	int e = l;
	int a = U[e],b = V[e];
	dist_a[a] = 0; 
	queue<int>q; q.push(a);
	while(!q.empty()){
		int cur = q.front(); q.pop();
		for(pi p : tree[cur]){
			int nxt = p.first;
			int id = p.second;
			if(dist_a[nxt] > dist_a[cur] + 1){
				dist_a[nxt] = dist_a[cur] + 1;
				q.push(nxt);
			}
		}
	}
	dist_b[b] = 0; 
	q.push(b);
	while(!q.empty()){
		int cur = q.front(); q.pop();
		for(pi p : tree[cur]){
			int nxt = p.first;
			int id = p.second;
			if(dist_b[nxt] > dist_b[cur] + 1){
				dist_b[nxt] = dist_b[cur] + 1;
				q.push(nxt);
			}
		}
	}
	vector<int>c1,c2;
	for(int i=0; i<n; i++){
		if(dist_a[i] < dist_b[i]) c1.emplace_back(i);
		if(dist_a[i] > dist_b[i]) c2.emplace_back(i);
	}
	answer(FIND(w,c1,a,e),FIND(w,c2,b,e));
}

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

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:49:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |  for(int i=0; i<U.size(); i++){
      |               ~^~~~~~~~~
highway.cpp:72:8: warning: unused variable 'id' [-Wunused-variable]
   72 |    int id = p.second;
      |        ^~
highway.cpp:85:8: warning: unused variable 'id' [-Wunused-variable]
   85 |    int id = p.second;
      |        ^~

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