Submission #933809

#	Time	Username	Problem	Language	Result	Execution time	Memory
933809		kim	Highway Tolls (IOI18_highway)	C++17	5 / 100	169 ms	12960 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],adj2[90005];
bitset<90005> vis;
int pre[90005];

vector<int> ans,tmp;
int dist;
int play(int n,vector<int> &U,vector<int> &V,int u0){
	for(int i=0;i<n;++i) adj2[i].clear();
	vis=0;
	int m=U.size();
	{
		queue<int> q;
		q.emplace(u0);
		vis[u0]=1;
		while(q.size()){
			int u=q.front(); q.pop();
			for(auto &v:adj1[u]){
				if(vis[v]) continue;
				vis[v]=1;
				q.emplace(v);
				adj2[u].eb(v);
			}
		}
	}
	{
		stack<pii> st;
		st.emplace(u0,u0);
		int id=-1;
		while(st.size()){
			auto [u,p]=st.top(); st.pop();
			pre[u]=++id;
			for(auto &v:adj2[u]){
				if(v!=p) st.emplace(v,u);
			}
		}
	}
	int l=0,r=n-1;
	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;
	}
	cerr<<pre[0]<<" "<<pre[1]<<" "<<pre[2]<<" "<<pre[3]<<'\n';
	for(int i=0;i<n;++i){
		if(pre[i]==l){
			ans.eb(i);
			return i;
		}
	}
}

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],0);
}

Compilation message (stderr)

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

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