Submission #1197053

#TimeUsernameProblemLanguageResultExecution timeMemory
1197053tkm_algorithms통행료 (IOI18_highway)C++20
0 / 100
7 ms2040 KiB
/** * In the name of Allah * We are nothing and you're everything **/ #include <bits/stdc++.h> #include "highway.h" using namespace std; using ll = long long; #define all(x) begin(x), end(x) #define sz(x) (int)(x).size() const char nl = '\n'; vector<int> w; const int NN = 9e4+5; int btree[NN]; // int ask(vector<int> w1) { // int cost = 0; // for (int i = 0; i < sz(w1); ++i) { // if (w1[i] == 1) { // if (i == 0)cost += 2; // } else // if (i == 0)cost += 1; // } // return cost; // } // void answer(int x, int y) { // cout << y; // } void find_pair(int N, vector<int> u, vector<int> v, int a, int b) { int m = sz(u), n = N; vector<pair<int, int>> g[n+1]; w.resize(m); for (int i = 0; i < m; ++i) { g[u[i]].push_back({v[i], i}); g[v[i]].push_back({u[i], i}); } ll cost = ask(w), len = cost/a; queue<pair<int, int>> q; // u, and par. q.push({0, 0}); int which = 1; while (!q.empty()) { int ux = q.front().first, p = q.front().second; q.pop(); for (auto i: g[ux]) { if (i.first == p)continue; btree[which++] = i.second; q.push({i.first, ux}); } } //int ans = -1; int l = 1, r = m+1; //cout << which << nl; //cout << l << " " << r << nl; while (r-l>1) { int mid = l+r>>1; for (int i = 1; i <= m; ++i) { int x = btree[i]; w[x] = 0; if (i >= mid)w[x] = 1; } ll d = ask(w); //cout << mid << " " << d << nl; if (d != cost)l = mid; else r = mid; } //for (int i = 0; i < m; ++i) //w[i] = 0; answer(0, v[btree[l]]); } //void solve() { //int n, m; cin >> n >> m; //vector<int> u(m), v(m); //for (int i = 0; i < m; ++i) { //cin >> u[i] >> v[i]; //} //find_pair(n, u, v, 1, 2); //} //int32_t main() { //ios::sync_with_stdio(0); //cin.tie(0); //int t = 1; //for (int _ = 0; _ < t; ++_) { //solve(); //} //return 0; //}
#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...