Submission #433964

#TimeUsernameProblemLanguageResultExecution timeMemory
433964AugustinasJucasHighway Tolls (IOI18_highway)C++14
51 / 100
300 ms262148 KiB
#include "highway.h" #include <bits/stdc++.h> using namespace std; const int dydis = 1e5 + 10; vector<pair<int, int> > gr[dydis]; int n, m; long long light, heavy; int tevas[dydis]; int dist[dydis]; int virs[dydis]; vector<pair<int, int> > brn; int getLen(){ vector<int> st; for(int i = 0; i < m; i++) st.push_back(0); return 1ll * ask(st) / light; } void dfs(int v, int came = -1, int dst = 0){ dist[v] = dst; if(came == -1) virs[v] = -1; for(auto x : gr[v]){ if(x.first == came) continue; tevas[x.first] = v; virs[x.first] = x.second; dfs(x.first, v, dst+1); } } vector<pair<int, int> > getInds(int v, int len){ // first - brianos indeksas, sec - virsunes dfs(v, -1); vector<pair<int, int> > ret; for(int i = 0; i < n; i++){ if(dist[i] != len) continue; ret.push_back({virs[i], i}); } return ret; } pair<int, int> solveWhenHave(int v, int len){ vector<pair<int, int> > inds = getInds(v, len); // cia turetu visi buti blogi, isskyrus viena! int l = 0; int r = inds.size()-1; int mid = -1; int kair = inds.size()-1; vector<int> askk(m, 0); long long turi = len * light; while(l <= r){ mid = (l + r) / 2; for(int i = 0; i <= mid; i++) askk[inds[i].first] = 1; if(ask(askk) != turi){ r = mid-1; kair = min(kair, mid); }else{ l = mid+1; } for(int i = 0; i <= mid; i++) askk[inds[i].first] = 0; } return {v, inds[kair].second}; } /* int findOne(int len){ //randa viena node'a vector<pair<int, int> > inds; for(int i = 0; i < (int) brn.size(); i++) inds.push_back({i, brn[i].first}); int l = 0; int r = inds.size()-1; int mid = -1; int kair = inds.size()-1; vector<int> askk(m, 0); long long turi = len * light; while(l <= r){ mid = (l + r) / 2; for(int i = 0; i <= mid; i++) askk[inds[i].first] = 1; if(ask(askk) != turi){ r = mid-1; kair = min(kair, mid); }else{ l = mid+1; } for(int i = 0; i <= mid; i++) askk[inds[i].first] = 0; } return inds[kair].second; }*/ int findAukste(vector<pair<int, int> > briaunos, int len){ int l = 0; int r = briaunos.size()-1; int mid; vector<int> st(m, 0); long long turi = 1ll * len * light; int desn = r; //cout << "briaunos: \n"; for(auto x : briaunos) cout << "briauna " << x.first << ", jos galas " << x.second << endl; cout << endl; while(l <= r){ mid = (l + r) / 2; for(int i = 0; i <= mid; i++) st[briaunos[i].first] = 1; if(ask(st) != turi){ r = mid-1; desn = min(desn, mid); }else{ l = mid+1; } for(auto & x : st) x = 0; } return briaunos[desn].second; } vector<pair<int, int> > aukstai[dydis]; int findFarthest(int v, int len){ dfs(v, -1); int mx = 0; for(int i = 0; i < n; i++){ aukstai[dist[i]].push_back({virs[i], i}); mx = max(mx, dist[i]); } int l = 1, r = mx, mid; long long turi = 1ll * len * heavy; vector<int> st(m, 0); int ans = 0; while(l <= r){ mid = (l + r) / 2; for(int i = 1; i <= mid; i++){ for(auto x : aukstai[i]) st[x.first] = 1; } if(ask(st) == turi){ r = mid-1; }else{ ans = max(ans, mid); l = mid+1; } for(auto &x : st) x = 0; } // galas yra ans aukste ans++; //cout << "galas yra " << ans << " aukste nuo " << v << endl; return findAukste(aukstai[ans], len); } pair<int, int> solveEil(int len){ long long turi = light * len; int leftmost = -1; int l = 0; int r = n-1; int mid; vector<int> st(m, 0); while(l <= r){ mid = (l + r) / 2; for(int i = 0; i <= mid; i++) st[i] = 1; if(ask(st) == turi){ leftmost = max(leftmost, mid); l = mid+1; }else{ r = mid-1; } for(int i = 0; i <= mid; i++) st[i] = 0; } //cout << "leftmost = " << leftmost << endl; int raitmost = n-1; l = 0; r = n-1; while(l <= r){ mid = (l + r) /2; for(int i = mid; i <= n-1; i++) st[i] = 1; if(ask(st) == turi){ raitmost = min(raitmost, mid); r = mid-1; }else{ l = mid+1; } for(int i = mid; i <= n-1; i++) st[i] = 0; } return {leftmost+1, raitmost}; } /* 6 5 5 7 1 3 0 1 1 2 2 3 3 4 4 5 */ void find_pair(int N, vector<int> U, vector<int> V, int A, int B) { n = N; m = V.size(); light = A; heavy = B; bool eile = 1; for(int i = 0; i < m; i++){ gr[U[i]].push_back({V[i], i}); gr[V[i]].push_back({U[i], i}); brn.push_back({V[i], U[i]}); if(!(U[i] == i && V[i] == i+1)) eile = 0; } int len = getLen(); if(eile){ auto ret = solveEil(len); answer(ret.first, ret.second); return ; } int uu = findFarthest(0, len); //cout << "galas yra " << uu << endl; auto ans = solveWhenHave(uu, len); answer(ans.first, ans.second); return ; } /* 12 11 5 7 6 10 0 2 0 3 2 4 2 5 3 6 3 7 4 8 5 9 8 10 8 11 9 1 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...