Submission #933831

#	Time	Username	Problem	Language	Result	Execution time	Memory
933831		kim	Highway Tolls (IOI18_highway)	C++17	5 / 100	154 ms	9936 KiB

highway

#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
#define eb emplace_back
using pii=pair<int,int>;
#define f first
#define s second

using ti3=tuple<int,int,int>;

vector<int> adj1[90005];
bitset<90005> vis;
int pre[90005],node[90005];

vector<int> ans,tmp;
int dist;
int play(int n,vector<int> &U,vector<int> &V,int u0){
	vis=0;
	int m=U.size();
	int id=0;
	{
		queue<int> q;
		q.emplace(u0);
		vis[u0]=1;
		while(q.size()){
			int u=q.front(); q.pop();
			pre[u]=++id;
			node[id]=u;
			for(auto &v:adj1[u]){
				if(vis[v]) continue;
				vis[v]=1;
				q.emplace(v);
			}
		}
	}
	int l=1,r=id;
	while(l<r){
		int mid=l+r>>1;
		for(int i=0;i<m;++i){
			if(pre[U[i]]<=mid&&pre[V[i]]<=mid) tmp[i]=0;
			else tmp[i]=1;
		}
		if(ask(tmp)==dist) r=mid;
		else l=mid+1;
	}
	ans.eb(node[l]);
	return node[l];
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
	for(int i=0;i<U.size();++i){
		adj1[U[i]].eb(V[i]);
		adj1[V[i]].eb(U[i]);
	}
	tmp.assign((int)U.size(),0);
	dist=ask(tmp);
	play(N,U,V,play(N,U,V,0));
	answer(ans[0],ans[1]);
}

Compilation message (stderr)

highway.cpp: In function 'int play(int, std::vector<int>&, std::vector<int>&, int)':
highway.cpp:38:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |   int mid=l+r>>1;
      |           ~^~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:51:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |  for(int i=0;i<U.size();++i){
      |              ~^~~~~~~~~

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