Submission #1210891

#TimeUsernameProblemLanguageResultExecution timeMemory
1210891garam1732Highway 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]; vector<vector<int> > adj1, adj2; queue<int> q; vector<ll> d1, d2; void bfs(int s, vector<ll> &d) { d[s] = 0; q.push(s); while(q.size()) { int here = q.front(); q.pop(); for(auto [there,w] : adj[here]) { if(d[there] > d[here]+1) { d[there] = d[here]+1; q.push(there); } } } } void bfs(int s, int t, vector<ll> &dst, vector<int>& v) { q.push(s); while(q.size()) { int here = q.front(); q.pop(); v.push_back(here); for(auto [there,w] : adj[here]) { if(dst[there] == dst[here]+1) { if(dst[there] < d2[there]+d1[there]-dst[there]) { q.push(there); } } } } } void answer(int p, int q); ll ask(vector<int> w); bool chk[MAXN]; vector<int> v1, v2; void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) { 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, 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) { lb = mid+1; } else { ub = mid; } } int e = lb; int x = U[e], y = V[e]; d1.resize(N, INF); d2.resize(N, INF); bfs(x, d1); bfs(y, d2); adj1.resize(N); adj2.resize(N); bfs(x, y, d1, v1); bfs(y, x, d2, v2); lb = 0, ub = (int)v1.size()-1, mid; while(lb < ub) { mid = lb+ub>>1; memset(chk, 0, sizeof chk); for(int i=0; i<=mid; 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; else lb = mid+1; } int p = v1[lb]; lb = 0, ub = (int)v2.size()-1, mid; while(lb < ub) { mid = lb+ub>>1; memset(chk, 0, sizeof chk); for(int i=0; i<=mid; 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; else lb = mid+1; } 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:70:17: error: call of overloaded 'ask(std::vector<int>&)' is ambiguous
   70 |     ll len = ask(w)/A;
      |              ~~~^~~
In file included from highway.cpp:1:
highway.h:7:11: note: candidate: 'long long int ask(const std::vector<int>&)'
    7 | long long ask(const std::vector<int> &w);
      |           ^~~
highway.cpp:58:4: note: candidate: 'll ask(std::vector<int>)'
   58 | ll ask(vector<int> w);
      |    ^~~
highway.cpp:76:21: error: call of overloaded 'ask(std::vector<int>&)' is ambiguous
   76 |         ll res = ask(w);
      |                  ~~~^~~
In file included from highway.cpp:1:
highway.h:7:11: note: candidate: 'long long int ask(const std::vector<int>&)'
    7 | long long ask(const std::vector<int> &w);
      |           ^~~
highway.cpp:58:4: note: candidate: 'll ask(std::vector<int>)'
   58 | ll ask(vector<int> w);
      |    ^~~
highway.cpp:102:23: error: call of overloaded 'ask(std::vector<int>&)' is ambiguous
  102 |         } ll res = ask(w);
      |                    ~~~^~~
In file included from highway.cpp:1:
highway.h:7:11: note: candidate: 'long long int ask(const std::vector<int>&)'
    7 | long long ask(const std::vector<int> &w);
      |           ^~~
highway.cpp:58:4: note: candidate: 'll ask(std::vector<int>)'
   58 | ll ask(vector<int> w);
      |    ^~~
highway.cpp:118:23: error: call of overloaded 'ask(std::vector<int>&)' is ambiguous
  118 |         } ll res = ask(w);
      |                    ~~~^~~
In file included from highway.cpp:1:
highway.h:7:11: note: candidate: 'long long int ask(const std::vector<int>&)'
    7 | long long ask(const std::vector<int> &w);
      |           ^~~
highway.cpp:58:4: note: candidate: 'll ask(std::vector<int>)'
   58 | ll ask(vector<int> w);
      |    ^~~