Submission #416974

#	Time	Username	Problem	Language	Result	Execution time	Memory
416974		balbit	Highway Tolls (IOI18_highway)	C++14	51 / 100	197 ms	13904 KiB

highway

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

#define ll long long
#define pii pair<int, int>
#define pb push_back
#define f first
#define s second

#define REP(i,n) for (int i = 0; i<n; ++i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)

#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()


#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<"- "<<#__VA_ARGS__<<": ", _do(__VA_ARGS__)
template<typename T> void _do(T && x) {cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S && ...y) {cerr<<x<<", ";}
#else
#define bug(...)

#endif // BALBIT
const int maxn=90005;
vector<int> ord;
int pe[maxn];
vector<pii> g[maxn];
ll toth;

void dfs(int v, int p) {
    ord.pb(v);
    for (pii e : g[v]) {
        int u = e.f;
        if (u != p) {
            pe[u] = e.s;
            dfs(u,v);
        }
    }
}

int n;

int lst(int rt) {
    ord.clear();
    memset(pe, -1, sizeof pe);
    dfs(rt, -1);
    int l = 1, r = n-1;
    while (l!=r) {
        int mid = (l+r)/2;
        vector<int> tmp(n-1);
        REP1(i,mid) {
            tmp[pe[ord[i]]] = 1;
        }
        if (ask(tmp) < toth) {
            // tot heavy
            l = mid+1;
        }else{
            r = mid;
        }
    }
    return ord[l];
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
  int M = U.size();
  n = N;
  REP(i,N-1) {
    g[U[i]].pb({V[i],i});
    g[V[i]].pb({U[i],i});
  }
  vector<int> tmp(N-1,1);
  toth=ask(tmp);
  int S = lst(0);
  int T = lst(S);
  answer(S,T);
}

/*
5 4 1 2 2 1
0 1
1 2
1 3
0 4
*/

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:67:7: warning: unused variable 'M' [-Wunused-variable]
   67 |   int M = U.size();
      |       ^

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