Submission #1210905

#TimeUsernameProblemLanguageResultExecution timeMemory
1210905garam1732Highway Tolls (IOI18_highway)C++20
Compilation error
0 ms0 KiB
#include "highway.h" #include <bits/stdc++.h> using namespace std; #define ff first #define ss second #define bl ' ' #define endl '\n' #define all(v) (v).begin(), (v).end() #define comp(v) (v).erase(unique(all(v)), (v).end()) #define lbd(v,x) lower_bound(all(v), (x))-(v).begin() #define ubd(v,x) upper_bound(all(v), (x))-(v).begin() typedef long long ll; typedef pair<int, int> pi; typedef pair<pi, int> pii; typedef pair<int, pi> ipi; typedef pair<pi, pi> pipi; typedef pair<ll, ll> pll; const int MAXN = 100100*1; const ll MOD = 998244353; const ll INF = 1e16; vector<pi> adj[MAXN]; bool chk[MAXN]; queue<pi> q; vector<ll> d; vector<int> v1, v2; void bfs(int s, int t) { d[s] = d[t] = 0; q.push(pi(s, 1)); q.push(pi(t, 2)); while(q.size()) { int here = q.front().ff; int col = q.front().ss; q.pop(); if(col == 1) v1.push_back(here); else v2.push_back(here); for(auto [there,w] : adj[here]) { if(d[there] > d[here]+1) { d[there] = d[here]+1; q.push(pi(there, col)); } } } } void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) { uu=U, vv=V; int m = U.size(); for(int i=0; i<m; i++) { adj[U[i]].push_back(pi(V[i], i)); adj[V[i]].push_back(pi(U[i], i)); } vector<int> w(m); ll len = ask(w)/A; int lb = 0, ub = m-1, mid; while(lb < ub) { mid = lb+ub>>1; w.clear(); w.resize(m); for(int i=0; i<=mid; i++) w[i]=1; ll res = ask(w); if(res > A*len) { ub = mid; } else { lb = mid+1; } } int e = lb; int x = U[e], y = V[e]; d.resize(N, INF); bfs(x, y); lb = 0, ub = (int)v1.size()-1, mid; while(lb < ub) { mid = lb+ub+1>>1; memset(chk, 0, sizeof chk); for(int i=mid; i<v1.size(); i++) chk[v1[i]]=1; w.clear(); w.resize(m); for(int i=0; i<m; i++) { if(chk[U[i]]!=chk[V[i]]) w[i]=1; } ll res = ask(w); if(res == A*len) ub = mid-1; else lb = mid; } int p = v1[lb]; lb = 0, ub = (int)v2.size()-1, mid; while(lb < ub) { mid = lb+ub+1>>1; memset(chk, 0, sizeof chk); for(int i=mid; i<v2.size(); i++) chk[v2[i]]=1; w.clear(); w.resize(m); for(int i=0; i<m; i++) { if(chk[U[i]]!=chk[V[i]]) w[i]=1; } ll res = ask(w); if(res == A*len) ub = mid-1; else lb = mid; } int q = v2[lb]; answer(p, q); }

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:47:79: error: 'uu' was not declared in this scope
   47 | void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) { uu=U, vv=V;
      |                                                                               ^~
highway.cpp:47:85: error: 'vv' was not declared in this scope; did you mean 'v2'?
   47 | void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) { uu=U, vv=V;
      |                                                                                     ^~
      |                                                                                     v2