Submission #625120

#	Time	Username	Problem	Language	Result	Execution time	Memory
625120		MateGiorbelidze	Highway Tolls (IOI18_highway)	C++14	51 / 100	970 ms	20796 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back

vector<int> g[90001] , ans;

vector<bool> used(90001);

map <pair<int,int>, int> mp;

vector<int> vask;

vector<int> v, u , a(130001), d(130001);

int n , m , sm , bg;
ll mn;

void bfs (int rt) {
    queue <int> q;
    q.push(rt);
    
    for (int i = 0; i < n; i++)
    	used[i] = 0;
    
    int timer = 0;
    while(!q.empty()){
    	
        int v = q.front();
        q.pop();
        used[v] = 1;
        
        for(int k : g[v]){
            if(used[k] != 0) continue;
            a[timer++] = mp[{v , k}];
            d[mp[{v , k}]] = k;
            
            q.push(k);
        }
        
    }
	
}

void find_ans(int rt) {
	
	int l = 0 , r = n - 2;
	
	bfs(rt);
	
	//cout<<d[4];
	while (l < r) {
		
		int mid = (l + r) / 2;
		
		for (int i = 0; i <= mid; i++) {
			
			vask[a[i]] = 0;
			
		}
		
		for (int i = mid + 1; i <= r; i++) {
			
			vask[a[i]] = 1;
			//cout<<a[i]<" ";
			
		}
		
		ll curs = ask(vask);
		
		if (curs > mn) l = mid + 1;
		else r = mid;
	}
	
	ans.pb(d[a[l]]);
	
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
  	n = N; u = U; v = V, sm = A; bg = B;
  	
  	m = u.size();
  	
  	
  	for (int i = 0; i < m; i++) {
  		vask.pb(0);
  		
  		g[u[i]].pb(v[i]);
  		g[v[i]].pb(u[i]);
  		
  		mp[{u[i] , v[i]}] = mp[{v[i] , u[i]}] = i;
	}
	
	mn = ask(vask);
	
	ll l = 0, r = n - 1;
	
	while (l < r) {
		
		ll mid = (l + r) / 2;
		
		for (int i = 0; i < m; i++)
			vask[i] = 1;
			
		for (int i = 0; i <= mid; i++) {
			
			for (auto k : g[i]) {
				
				vask[mp[{i , k}]] = 0;
				
			}
			
		}	
		
		ll curs = ask(vask);
		
		if (curs == mn) r = mid;
		else l = mid + 1;
				
		
	}
	
	find_ans(l);
	//cout<<ans[0];
	find_ans(ans[0]);
	//cout<<ans[1];
	//cout<<d[a[l]];
	
	answer(ans[0] , ans[1]);
	
}

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