Submission #933839

#	Time	Username	Problem	Language	Result	Execution time	Memory
933839		kim	Highway Tolls (IOI18_highway)	C++17	5 / 100	221 ms	11012 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

int N,M;
vector<int> adj1[90005];
bool vis[90005];
int pre[90005],node[90005];
pii edge[130005];

vector<int> ans,tmp;
int dist;

int id0;
void bfs(int u){
  queue<int> q;
  q.push(u);
  vis[u]=1;
  while(q.size()){
    int u=q.front(); q.pop();
    pre[u]=++id0;
    node[id0]=u;
    for(auto &v:adj1[u]){
      if(!vis[v]){
        q.push(v);
        vis[v]=1;
      }
    }
  }
}

int play(int u0){
	for(int i=0;i<N;++i) vis[i]=0;
	id0=0;
	bfs(u0);

	// int l=1,r=id0;
	// while(l<r){
	// 	int mid=l+r>>1;
	// 	for(int i=0;i<M;++i){
	// 		auto &[u,v]=edge[i];
	// 		if(pre[u]<=mid&&pre[v]<=mid) tmp[i]=0;
	// 		else tmp[i]=1;
	// 	}
	// 	if(ask(tmp)==dist) r=mid;
	// 	else l=mid+1;
	// }

	  int l=1,r=id0;
	while(l<r){
		int mid=l+((r-l)>>1);
	
		for(int i=0;i<M;++i){
		auto &[u,v]=edge[i];
		if(pre[u]<=mid&&pre[v]<=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) {
	::N=N,M=U.size();
	for(int i=0;i<U.size();++i){
		adj1[U[i]].eb(V[i]);
		adj1[V[i]].eb(U[i]);
		edge[i]={U[i],V[i]};
		tmp.eb(0);
	}
	dist=ask(tmp);
	play(play(0));
	answer(ans[0],ans[1]);
}

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:73:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |  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