Submission #530065

#	Time	Username	Problem	Language	Result	Execution time	Memory
530065		qwerasdfzxcl	Highway Tolls (IOI18_highway)	C++14	100 / 100	309 ms	19052 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
vector<pair<int, int>> adj[100100], G[100100];
vector<int> w, rans;
int n, m, a, b, P[100100], E[100100], par[100100], cnt = -1;
ll c0;

vector<int> shit, tihs, fuck, kcuf;

ll myask(vector<int> &w){
    vector<int> w2(m);
    for (int i=0;i<m;i++) w2[i] = w[fuck[i]];
    return ask(w2);
}

int hash_val;
void init(){
    mt19937 seed(1234);
    shit.resize(n); tihs.resize(n);
    fuck.resize(m); kcuf.resize(m);
    for (int i=0;i<n;i++) shit[i] = i;
    for (int i=0;i<m;i++) fuck[i] = i;

    if (hash_val<125'000'000 && hash_val>=0) shuffle(shit.begin(), shit.end(), seed);
    if (hash_val<125'000'000 && hash_val>=0) shuffle(fuck.begin(), fuck.end(), seed);

    for (int i=0;i<n;i++) tihs[shit[i]] = i;
    for (int i=0;i<m;i++) kcuf[fuck[i]] = i;
}

int search1(){
    int l = 0, r = n-1, ans = -1;
    while(l<=r){
        int m = (l+r)>>1;
        fill(w.begin(), w.end(), 0);
        for (int i=0;i<=m;i++) for (auto &[v, j]:adj[i]) w[j] = 1;

        if (myask(w)==c0) ans = m, l = m+1;
        else r = m-1;
    }

    fill(w.begin(), w.end(), 0);
    for (int i=0;i<=ans;i++) for (auto &[v, j]:adj[i]) w[j] = 1;
    return ans + 1;
}

bool visited[100100];
void bfs(int s){
    queue<int> q;
    q.push(s);
    visited[s] = 1;
    while(!q.empty()){
        int cur = q.front(); q.pop();
        for (auto &[nxt, i]:adj[cur]) if (!w[i] && !visited[nxt]){
            G[cur].emplace_back(nxt, i);
            G[nxt].emplace_back(cur, i);
            visited[nxt] = 1;
            w[i] = -1;
            q.push(nxt);
        }
    }
}

void dfs(int s, int pa = -1, int idx = -1, int val = 0){
    P[++cnt] = s;
    E[cnt] = idx;
    par[cnt] = val;

    int tmp = cnt;
    for (auto &[v, i]:G[s]) if (v!=pa){
        dfs(v, s, i, tmp);
    }
}

int search2(int mx){
    int l = 1, r = mx, ans = mx+1;
    while(l<=r){
        int m = (l+r)>>1;
        for (int i=1;i<=cnt;i++) w[E[i]] = 0;
        for (int i=m;i<=mx;i++) w[E[i]] = 1;

        if (myask(w)==c0) ans = m, r = m-1;
        else l = m+1;
    }
    rans.push_back(P[--ans]);

    if (ans==0) return 0;
    for(;par[ans];ans=par[ans]);
    //printf("ret: %d\n", ans);
    return ans;
}

const int DIG = 123437, MOD = 1e9+7;

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
    n = N, a = A, b = B, m = U.size();
    for (int i=0;i<m;i++) hash_val = ((ll)hash_val * DIG + U[i]) % MOD;
    init();
    for (int i=0;i<m;i++){
        U[i] = shit[U[i]], V[i] = shit[V[i]];
        adj[U[i]].emplace_back(V[i], fuck[i]);
        adj[V[i]].emplace_back(U[i], fuck[i]);
    }

    w.resize(m);
    c0 = myask(w);

    int x = search1();
    bfs(x);
    for (int i=0;i<m;i++){
        if (w[i]==-1) w[i] = 0;
        else w[i] = 1;
    }
    dfs(x);

    /*printf("x: %d\n", x);
    printf("E: ");
    for (int i=0;i<=cnt;i++) printf("%d ", E[i]);
    printf("\nP: ");
    for (int i=0;i<=cnt;i++) printf("%d ", P[i]);
    printf("\npar: ");
    for (int i=0;i<=cnt;i++) printf("%d ", par[i]);
    printf("\n");*/

    search2(search2(cnt)-1);
    answer(tihs[rans[0]], tihs[rans[1]]);
}

Compilation message (stderr)

highway.cpp: In function 'int search1()':
highway.cpp:39:43: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   39 |         for (int i=0;i<=m;i++) for (auto &[v, j]:adj[i]) w[j] = 1;
      |                                           ^
highway.cpp:46:41: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   46 |     for (int i=0;i<=ans;i++) for (auto &[v, j]:adj[i]) w[j] = 1;
      |                                         ^
highway.cpp: In function 'void bfs(int)':
highway.cpp:57:20: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   57 |         for (auto &[nxt, i]:adj[cur]) if (!w[i] && !visited[nxt]){
      |                    ^
highway.cpp: In function 'void dfs(int, int, int, int)':
highway.cpp:73:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   73 |     for (auto &[v, i]:G[s]) if (v!=pa){
      |                ^

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