Submission #1052285

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052285		ReLice	Highway Tolls (IOI18_highway)	C++17	90 / 100	140 ms	11292 KiB

highway

    #include "highway.h"
     
    #include <bits/stdc++.h>
     
    using namespace std;
     
    #define all(x) x.begin(), x.end()
    #define ar array
    #define pb push_back
    #define ln '\n'
    //#define int long long
     
    using i64 = long long;
     
    template <class F, class _S>
    bool chmin(F &u, const _S &v){
        bool flag = false;
        if ( u > v ){
            u = v; flag |= true;
        }
        return flag;
    }
     
    template <class F, class _S>
    bool chmax(F &u, const _S &v){
        bool flag = false;
        if ( u < v ){
            u = v; flag |= true;
        }
        return flag;
    }
     
    void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
    	int n = N, M = U.size();
    	
    	vector <vector<ar<int,2>>> adj(n);
    	
    	for ( int i = 0; i < M; i++ ){
    		adj[U[i]].pb({V[i], i});
    		adj[V[i]].pb({U[i], i});
    	}
    	
    	vector <int> w(M);
    	
    	i64 C = ask(w);
    	
    	int l = 0, r = n - 1, ans;
    	
    	while ( l <= r ){
    		int m = (l + r) / 2;
    		
    		if ( r - l > 60000 ) m = 60000;
    		
    		w.assign(M, 0);
    		
    		for ( int u = m + 1; u < n; u++ ){
    			for ( auto &[v, j]: adj[u] ){
    				w[j] = 1;
    			}
    		}
    		
    		if ( ask(w) == C ){
    			ans = m;
    			r = m - 1;
    		} else l = m + 1;
    	}
    	
    	int root = ans;
    	
    	vector <int> fa(n), ls, us(n);
    	
    	queue <int> q;
    	
    	q.push(root); us[root] = 1;
    	
    	while ( !q.empty() ){
    		int u = q.front();
    		q.pop();
    		
    		ls.pb(u);
    		
    		for ( auto &[v, j]: adj[u] ){
    			if ( us[v] ) continue;
    			
    			us[v] = 1;
    			fa[v] = u;
    			q.push(v);
    		}
    	}
    	
    	vector <int> e(n, -1);
    	
    	for ( int u = 0; u < n; u++ ){
    		for ( auto &[v, j]: adj[u] ){
    			if ( fa[u] == v ){
    				e[u] = j;
    			}
    		}
    	}
    	
    	l = 1, r = n - 1;
    	
    	while ( l <= r ){
    		int m = (l + r) / 2;
    		
    		w.assign(M, 1);
    		
    		for ( int i = 1; i <= m; i++ ){
    			w[e[ls[i]]] = 0;
    		}
    		
    		if ( ask(w) == C ){
    			ans = m;
    			r = m - 1;
    		} else l = m + 1;
    	}
    	
    	int sx = ls[ans];
    	
    	vector <int> pth;
    	
    	{ // path from sx to root
    		int it = sx;
    		
    		while ( it != root ){
    			pth.pb(e[it]);
    			it = fa[it];
    		}
    	}
    	
    	l = 0, r = ans - 1;
    	
    	while ( l <= r ){
    		int m = (l + r) / 2;
    		
    		w.assign(M, 1);
    		
    		for ( auto &j: pth ) w[j] = 0;
    		
    		for ( int i = 0; i < m; i++ ){
    			w[e[ls[i + 1]]] = 0;
    		}
    		
    		if ( ask(w) == C ){
    			ans = m;
    			r = m - 1;
    		} else l = m + 1;
    	}
    	
    	int se = ls[ans];
    	
    	answer(sx, se);
    }

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:125:18: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
  125 |       while ( it != root ){
      |               ~~~^~~~~~~

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