Submission #158150

#	Time	Username	Problem	Language	Result	Execution time	Memory
158150		kig9981	Highway Tolls (IOI18_highway)	C++17	0 / 100	28 ms	2964 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>

using namespace std;

vector<int> adj[90000];
int g[90000], gsz[90000];

void find_pair(int N, vector<int> U, vector<int> V, int A, int B)
{
	int M=U.size(), sg=0, tg=0, gnum=0, s, t;
	vector<int> W(M);
	long long dist=ask(W);
	queue<int> Q;
	gsz[0]=N;
	for(int i=0;i<M;i++) {
		adj[U[i]].push_back(V[i]);
		adj[V[i]].push_back(U[i]);
	}
	while(gsz[sg]>1) {
		int c;
		long long t;
		for(int i=0;i<N;i++) if(sg==g[i]) {
			c=i;
			break;
		}
		Q.push(c);
		g[c]=++gnum;
		gsz[gnum]=1;
		while(!Q.empty()) {
			c=Q.front();
			Q.pop();
			for(auto n: adj[c]) if(gsz[gnum]<gsz[sg] && g[n]==sg) {
				g[n]=gnum;
				gsz[sg]--;
				gsz[gnum]++;
				Q.push(n);
			}
		}
		for(int i=0;i<M;i++) W[i]=g[U[i]]==gnum || g[V[i]]==gnum;
		if(ask(W)>dist) sg=gnum;
	}
	for(int i=0;i<N;i++) if(g[i]==sg) {
		s=i;
		break;
	}
	gsz[gnum=0]=N;
	for(int i=0;i<N;i++) g[i]=0;
	while(gsz[tg]>1) {
		int c;
		for(int i=0;i<N;i++) if(tg==g[i]) {
			c=i;
			break;
		}
		Q.push(c);
		g[c]=++gnum;
		gsz[gnum]=1;
		while(!Q.empty()) {
			c=Q.front();
			Q.pop();
			for(auto n: adj[c]) if(gsz[gnum]<gsz[tg] && g[n]==tg) {
				g[n]=gnum;
				gsz[tg]--;
				gsz[gnum]++;
				Q.push(n);
			}
		}
		for(int i=0;i<M;i++) W[i]=g[U[i]]==gnum || g[V[i]]==gnum;
		if(ask(W)>dist) {
			if(g[s]==gnum) {
				for(int i=0;i<M;i++) W[i]=g[U[i]]==tg || g[V[i]]==tg;
				if(ask(W)>dist) continue;
			}
			tg=gnum;
		}
	}
	for(int i=0;i<N;i++) if(g[i]==tg) {
		t=i;
		break;
	}
	answer(s,t);
}

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:22:13: warning: unused variable 't' [-Wunused-variable]
   long long t;
             ^
highway.cpp:81:8: warning: 't' may be used uninitialized in this function [-Wmaybe-uninitialized]
  answer(s,t);
  ~~~~~~^~~~~
highway.cpp:81:8: warning: 's' may be used uninitialized in this function [-Wmaybe-uninitialized]

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