Submission #292383

#	Time	Username	Problem	Language	Result	Execution time	Memory
292383		zoooma13	Highway Tolls (IOI18_highway)	C++14	45 / 100	337 ms	19952 KiB

highway

#include <bits/stdc++.h>
#include "highway.h"
using namespace std;

vector<vector <pair<int ,int>>> adj;

vector <pair<int ,int>> ver;
void dfs(int u ,int p=-1 ,int f=-1){
    for(auto&e : adj[u]) if(e.first != p)
        dfs(e.first ,u ,e.second);
    ver.push_back({u ,f});
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
    int M = U.size();
    adj.resize(N);
    for(int i=0; i<M; i++){
        adj[U[i]].push_back({V[i] ,i});
        adj[V[i]].push_back({U[i] ,i});
    }

    long long emp = ask(vector<int>(M ,0));

    int st = 0 ,en = M-1 ,mid;
    while(st <= en){
        mid = (st+en)>>1;
        vector <int> t(mid+1 ,1);
        t.resize(M);
        if(ask(t) != emp)
            en = mid-1;
        else
            st = mid+1;
    }

    int root = U[st];
    vector <int> intree(M ,1);

    queue <int> q{{root}};
    vector <bool> vis(N);
    vector <vector<pair<int ,int>>> newadj(N);
    while(!q.empty()){
        int u = q.front(); q.pop();
        for(auto&e : adj[u]) if(!vis[e.first]){
            q.push(e.first);
            vis[e.first] = 1;
            intree[e.second] = 0;
            newadj[u].push_back({e.first ,e.second});
            newadj[e.first].push_back({u ,e.second});
        }
    }

    swap(adj ,newadj);

    int S ,T;
    ver.clear() ,dfs(root) ,ver.pop_back();
    st = 0 ,en = M-1 ,mid;
    while(st <= en){
        mid = (st+en)>>1;
        vector <int> t = intree;
        for(int i=st; i<=mid; i++)
            t[ ver[i].second ] = 1;
        if(ask(t) != emp)
            en = mid-1;
        else
            st = mid+1;
    }
    S = ver[st].first;
    ver.clear() ,dfs(S) ,ver.pop_back();
    st = 0 ,en = M-1 ,mid;
    while(st <= en){
        mid = (st+en)>>1;
        vector <int> t = intree;
        for(int i=st; i<=mid; i++)
            t[ ver[i].second ] = 1;
        if(ask(t) != emp)
            en = mid-1;
        else
            st = mid+1;
    }
    T = ver[st].first;
    answer(S ,T);
}

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:56:26: warning: right operand of comma operator has no effect [-Wunused-value]
   56 |     st = 0 ,en = M-1 ,mid;
      |                          ^
highway.cpp:69:26: warning: right operand of comma operator has no effect [-Wunused-value]
   69 |     st = 0 ,en = M-1 ,mid;
      |                          ^

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