Submission #497158

#	Time	Username	Problem	Language	Result	Execution time	Memory
497158		MohamedFaresNebili	Highway Tolls (IOI18_highway)	C++14	0 / 100	251 ms	262148 KiB

highway

#include<bits/stdc++.h>
#include "highway.h"
 
        using namespace std;
 
        using ll  = long long;
        using ii = pair<int, int>;
        using vi  = vector<int>;
 
        #define pb push_back
        #define ff first
        #define ss second
        #define lb lower_bound
        #define all(x) (x).begin() , (x).end()
 
        vector<ii> adj[2*100005]; int par[2*100005], dep[2*100005];
        void dfs(int v, int p) {
            dep[v] = dep[p] + 1;
            for(auto u : adj[v]) {
                if(u.ff == p) continue;
                par[u.ff] = u.ss; dfs(u.ff, v);
            }
        }
 
        void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
            int M = U.size();
            vector<int> w(M, 0); ll k = ask(w);
            k /= A;
            for(int l = 0; l < M; l++) {
                int u = U[l], v = V[l];
                adj[u].pb({v, l}); adj[v].pb({u, l});
            }
            dep[0] = -1; dfs(0, 0);
            vector<int> ve;
            for(int l = 0; l < N; l++) {
                if(dep[l] != k) continue;
                ve.push_back(l);
            }
            for(auto u : ve) {
                int id = par[u]; w[id] = 1; ll curr = ask(w);
                if(curr > k) {
                    answer(u, 0); return;
                }
            }
            answer(0, N - 1);
        }

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