Submission #625097

#	Time	Username	Problem	Language	Result	Execution time	Memory
625097		MateGiorbelidze	Highway Tolls (IOI18_highway)	C++14	0 / 100	20 ms	4948 KiB

highway

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

vector<int> g[90001];

vector<bool> used(90001);

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

std::vector<int> v, u , a(130001);
int n , m , sm , bg , timer;

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

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();
  	
  	vector<int> vask;
  	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;
	}
	
	ll mn = ask(vask);
	
	int l = 0 , r = n - 2;
	
	bfs(0);
	
	
	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;
			
		}
		
		ll curs = ask(vask);
		
		if (curs > mn) l = mid + 1;
		else r = mid;
	}
	
	answer(l , 0);
	
}

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