Submission #599930

#	Time	Username	Problem	Language	Result	Execution time	Memory
599930		MohamedFaresNebili	Highway Tolls (IOI18_highway)	C++14	100 / 100	397 ms	27796 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;
 
                int M, res = -1, D[100005][2];
				ll ST;
                vector<int> adj[100005];
                map<int, int> Key[100005];
 
                void BFS(int v, int state) {
                    queue<int> Q; Q.push(v); D[v][state] = 0;
                    while(!Q.empty()) {
                        int A = Q.front(); Q.pop();
                        for(auto u : adj[A]) {
                            if(D[u][state] > D[A][state] + 1) {
                                D[u][state] = D[A][state] + 1;
                                Q.push(u);
                            }
                        }
                    }
                }
                int solve(int v, int state) {
                    queue<int> Q; Q.push(v);
                    vector<int> E, dep(100005, -1);
                    vector<pair<int, int>> P;
                    dep[v] = 0;
                    while(!Q.empty()) {
                        int A = Q.front(); Q.pop();
                        for(auto u : adj[A]) {
                            int K = Key[A][u];
                            if(D[u][state] < D[u][1 - state]) {
                                if(dep[u] == -1) {
                                    dep[u] = dep[A] + 1;
                                    Q.push(u); P.push_back({K, u});
                                }
                                else if(dep[u] == dep[A] + 1)
                                    E.push_back(K);
                            }
                            else if(K != res) E.push_back(K);
                        }
                    }
                    if(P.empty()) return v;
                    int lo = 0, hi = P.size() - 1, C = -1;
                    vector<int> V(M, 0);
                    for(auto u : E) V[u] = 1;
                    reverse(P.begin(), P.end());
                    while(lo <= hi) {
                        int md = (lo + hi) / 2;
                        vector<int> R = V;
                        for(int l = 0; l <= md; l++)
                            R[P[l].ff] = 1;
                        if(ask(R) > ST)
                            C = md, hi = md - 1;
                        else lo = md + 1;
                    }
                    if(C == -1) return v;
                    return P[C].ss;
                }
 
                void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
                    M = U.size(); ST = ask(vector<int>(M, 0));
                    for(int l = 0; l < N; l++)
                        D[l][0] = D[l][1] = 1e9 + 7;
                    for(int l = 0; l < M; l++) {
                        int X = U[l], Y = V[l];
                        adj[X].push_back(Y);
                        adj[Y].push_back(X);
                        Key[X][Y] = Key[Y][X] = l;
                    }
                    int lo = 0, hi = M - 1;
                    while(lo <= hi) {
                        int md = (lo + hi) / 2;
                        vector<int> C(M, 0);
                        for(int l = 0; l <= md; l++) C[l] = 1;
                        ll E = ask(C);
                        if(E > ST) res = md, hi = md - 1;
                        else lo = md + 1;
                    }
                    int X = U[res], Y = V[res];
                    BFS(X, 0); BFS(Y, 1);
                    int S = solve(X, 0), T = solve(Y, 1);
                    answer(S, T);
                }

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