Submission #1058207

#	Time	Username	Problem	Language	Result	Execution time	Memory
1058207		ReLice	Highway Tolls (IOI18_highway)	C++17	90 / 100	131 ms	28548 KiB

highway

    #include "highway.h"
    #include <bits/stdc++.h>
    #define ll long long
    #define vll vector<ll>
    #define pb push_back
    #define pf push_front
    #define sz size()
    #define bc back()
    #define pob pop_back()
    #define pof pop_front()
    #define fr first
    #define sc second
    using namespace std;
    const ll N=2e5+7;
    const ll inf=1e18;
    vector<vector<array<ll,2>>> g(N), g2(N);
    void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
    	ll M = V.sz;
    	ll s, t, rt;
    	ll n = N;
    	vll v, u;
    	ll i;
    	
    	for(auto i : V) v.pb(i);
    	for(auto i : U) u.pb(i);
    	
    	vector<int> w(M, 0);
    	
    	ll x = ask(w);
    	
    	for(i=0;i<M;i++){
    		g[v[i]].pb({u[i], i});
    		g[u[i]].pb({v[i], i});
    	}
    	
    	{//getting vertex on the path
    		ll l = 0, r = n;
    		while(l + 1 < r){
    			ll m = (l + r) / 2;
    			
    			if(r - l > 60000) m = 60000;
    			
    			w.assign(M, 0);
    			
    			for(i=0;i<m;i++){
    				for(auto [to, r] : g[i]) w[r] = 1;
    			}
    			
    			ll y = ask(w);
    			
    			if(y == x) l = m;
    			else r = m;
    		}
    		
    		rt = r - 1;
    	}
    	
    	vll p(n), d(n);
    	vll pr(n), tour;
    	vector<vll> dd(n);
    	
    	auto bfs = [&](ll s){
    		for(i=0;i<n;i++){
    			dd[i].clear();
    			d[i] = inf;
    			pr[i] = p[i] = -1;
    		}
    		
    		queue<ll> q;
    		q.push(s);
    		d[s] = 0;
    		
    		while(q.size()){
    			ll x = q.front();
    			q.pop();
    			
    			dd[d[x]].pb(x);
    			
    			for(auto [to, r] : g[x]){
    				if(d[to] > d[x] + 1){
    					d[to] = d[x] + 1 ;
    					pr[to] = r;
    					p[to] = x;
    					q.push(to);
    				}
    			}
    		}
    		
    		tour.clear();
    		for(i=0;i<n;i++){
    			for(auto j : dd[i]) tour.pb(j);
    		}
    	};
    	
    	vll path;
    	auto calc = [&](ll N){
    		ll l = 0, r = N;
    		while(l + 1 < r){
    			ll m = (l + r) / 2;
    			
    			if(r - l > 60000) m = 60000;
    			
    			w.assign(M, 1);
    			
    			for(auto i : path) w[i] =0;
    			
    			//~ cout<<m<<endl;
    			for(i=1;i<m;i++) {
    				w[pr[tour[i]]] = 0;
    				//~ cout<<v[pr[tour[i]]]<<' '<<u[pr[tour[i]]]<<endl;
    			}
    			
    			ll y = ask(w);
    				
    			if(x == y) r = m;
    			else l = m;
    		}
    		
    		return r - 1;
    	};
    	
    	bfs(rt);
    	
    	ll k = calc(n);
    	s = tour[k];
    	
    	{
    		ll x = s;
    		while(x != rt){
    			path.pb(pr[x]);
    			x = p[x];
    		}
    	}
    	
    	t = tour[calc(k)];
    	
    	answer(s, t);
    }

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