Submission #599741

#	Time	Username	Problem	Language	Result	Execution time	Memory
599741		MohamedFaresNebili	Highway Tolls (IOI18_highway)	C++14	12 / 100	223 ms	41932 KiB

highway

#include <bits/stdc++.h>
#include "highway.h"
/// #pragma GCC optimize ("Ofast")
/// #pragma GCC target ("avx2")
/// #pragma GCC optimize("unroll-loops")
 
                using namespace std;
 
                using ll = long long;
                using ld = long double;
                using ii = pair<ll, ll>;
                using vi = vector<int>;
 
                #define ff first
                #define ss second
                #define pb push_back
                #define all(x) (x).begin(), (x).end()
                #define lb lower_bound
 
                const int MOD = 1e9 + 7;
 
    vector<int> adj[100005], D[100005];
    map<int, int> K[100005];
    int P[100005];
    void dfs(int v, int p, int d) {
        D[d].push_back(v); P[v] = p;
        for(auto u : adj[v]) {
            if(u == p) continue;
            dfs(u, v, d + 1);
        }
    }
 
    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 E = ask(W); E /= A;
        for(int l = 0; l < M; l++) {
            int X = U[l], Y = V[l];
            K[X][Y] = K[Y][X] = l;
            adj[X].push_back(Y);
            adj[Y].push_back(X);
        }
        dfs(0, 0, 0);
        int lo = 0, hi = D[E].size() - 1, res = 0;
        while(lo <= hi) {
            int md = (lo + hi) / 2;
            for(int l = 0; l <= md; l++) {
                W[K[D[E][l]][P[D[E][l]]]] = 1;
            }
            ll C = ask(W);
            for(int l = 0; l <= md; l++) {
                W[K[D[E][l]][P[D[E][l]]]] = 0;
            }
            if(C > E * A) res = D[E][md], hi = md - 1;
            else lo = md + 1;
        }
        answer(0, res);
    }

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