Submission #294585

#	Time	Username	Problem	Language	Result	Execution time	Memory
294585		Gurban	Highway Tolls (IOI18_highway)	C++17	100 / 100	469 ms	11080 KiB

highway

#include <bits/stdc++.h>
#include "highway.h"
using namespace std;
#define pb push_back
#define ss second
#define ff first
#define sz(a) int(a.size())
#define all(a) a.begin(),a.end()
typedef long double ld;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
const ll inf = 1e18;
const int mod = 1e9+7; //998244353;
const int maxn = 1e5+5;
const int Xg[4] = {1,0,-1,0}, Yg[4] = {0,1,0,-1};
ll modpw(ll a,ll e) {if(e==0)return 1;ll x=modpw(a*a%mod,e>>1);return e&1?x*a%mod:x;}

int M;
vi col,C,D;
ll init;
queue<pii>q;
int dis[maxn];
vector<pii> adj[maxn];

int bin(vi v){
	
	int l = 0,r = sz(v) - 1,md,jog=0;
	
	while(l <= r){
		md = (l+r)/2;
		
		for(int i = 0;i < M;i++) col[i]=0;
		for(int i = md;i < sz(v);i++)
			for(auto j : adj[v[i]]) col[j.ss]=1;

		ll now=ask(col);

		if(now != init) l=md+1,jog=md;
		else r=md-1;
	}
	return v[jog];
}

void find_pair(int N, vi U, vi V, int A, int B) {
	M = sz(U); col.resize(M);
	for(int i = 0;i < M;i++){adj[U[i]].pb({V[i],i});adj[V[i]].pb({U[i],i});}
	
	init = ask(col);

	int l = 0,r = M-1,md,jog=0;
	while(l <= r){
		md = (l+r)/2;
		for(int i = 0;i <= md;i++) col[i]=1;
		for(int i = md+1;i < M;i++) col[i]=0;

		ll now=ask(col);

		if(now != init) r=md-1,jog=md;
		else l=md+1;
	}

	q.push({U[jog],1}); dis[U[jog]]=1;
	q.push({V[jog],2}); dis[V[jog]]=2;

	while(!q.empty()){

		int x=q.front().ff;
		int y=q.front().ss;
		
		q.pop();
		
		if(y==1) C.pb(x);
		else D.pb(x);
		
		for(auto i : adj[x]){
			if(dis[i.ff]) continue;
			dis[i.ff]=y;
			q.push({i.ff,y});
		}
	}

	int ans=bin(C);
	int ans1=bin(D);

	answer(ans,ans1);
}

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