Submission #767305

#TimeUsernameProblemLanguageResultExecution timeMemory
767305minhcoolTwo Transportations (JOI19_transportations)C++17
6 / 100
552 ms27316 KiB
#include "Azer.h" #define local #ifndef local #include "" #endif #include<bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; using namespace std; //#define int long long #define fi first #define se second #define pb push_back #define mp make_pair typedef pair<int, int> ii; typedef pair<ii, int> iii; typedef pair<ii, ii> iiii; const int N = 3e5 + 5; const int oo = 1e9 + 7, mod = 1e9 + 7; //mt19937 rng(1); /* int rnd(int l, int r){ int temp = rng() % (r - l + 1); return abs(temp) + l; }*/ /* Algo: N times: A gives B the value (x - lst) (lst = last value) B gives A the value (y - lst) if(x < y) -> A give info to B, else B give info to A Just like that. */ int n; vector<ii> Adj[N]; vector<iii> edges; priority_queue<ii, vector<ii>, greater<ii>> pq1; void send1(int x, int bits){ for(int i = 0; i < bits; i++){ SendA((x & (1LL << (bits - i - 1))) != 0); } } int answer[N]; bool done[N]; int phase, rem; int lst, pls, node; int a = 0, b = 0; void InitA(int N, int A, vector<int> U, vector<int> V, vector<int> C) { n = N; for(int i = 1; i < n; i++) answer[i] = oo; for(int i = 0; i < A; i++){ Adj[U[i]].pb({V[i], C[i]}); Adj[V[i]].pb({U[i], C[i]}); //edges.pb({{U[i], V[i]}, C[i]}); } for(auto it : Adj[0]){ int v = it.fi, w = it.se; if(answer[v] > answer[b] + w){ answer[v] = answer[b] + w; pq1.push({answer[v], v}); } } phase = 0, rem = 9; pls = 511, node = 2047; while(!pq1.empty()){ int u = pq1.top().se, d = pq1.top().fi; if(done[u]){ pq1.pop(); continue; } //send1(d - lst, 9); pls = d - lst; node = u; break; } done[0] = 1; send1(pls, 9); } void ReceiveA(bool x) { // cout << phase << " " << rem << "\n"; rem--; if(!phase) a = a * 2 + x; else b = b * 2 + x; if(rem) return; if(!phase){ // cout << "COMPARING " << a << " " << pls << "\n"; if(pls < a){ send1(node, 11); } else{ //a = pls; phase = 1; rem = 11; return; } } // cout << "OK\n"; if(a > pls) b = node; a = min(a, pls); answer[b] = a + lst; lst += a; //cout << "DONE " << b << "\n"; done[b] = 1; for(auto it : Adj[b]){ int v = it.fi, w = it.se; if(answer[v] > answer[b] + w){ answer[v] = answer[b] + w; pq1.push({answer[v], v}); } } bool ck = 0; for(int i = 0; i < n; i++) ck |= (!done[i]); if(!ck) return; // lst = a; a = b = 0; phase = 0, rem = 9; pls = 511, node = 2047; while(!pq1.empty()){ int u = pq1.top().se, d = pq1.top().fi; if(done[u]){ pq1.pop(); continue; } //send1(d - lst, 9); pls = d - lst; phase = 0; rem = 9; node = u; break; } // if(pq1.empty() && pls == 511) return; // cout << "CAN A " << lst << " " << node << " " << pls << "\n"; send1(pls, 9); } vector<int> Answer() { vector<int> v; for(int i = 0; i < n; i++) v.pb(answer[i]); return v; }
#include "Baijan.h" #define local #ifndef local #include "" #endif #include<bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; using namespace std; //#define int long long #define fi first #define se second #define pb push_back #define mp make_pair typedef pair<int, int> ii; typedef pair<ii, int> iii; typedef pair<ii, ii> iiii; const int N = 3e5 + 5; const int oo = 1e9 + 7, mod = 1e9 + 7; mt19937 rng(1); int rnd(int l, int r){ int temp = rng() % (r - l + 1); return abs(temp) + l; } int n2; vector<ii> Adj2[N]; priority_queue<ii, vector<ii>, greater<ii>> pq2; int answer2[N], done2[N]; int aa = 0, bb = 0; // lst length, phase 0/1, remmaining bits until done, minimum node, minimum dist - lst length int lstt, phasee, remm, nodee, plss; void InitB(int N, int B, vector<int> S, vector<int> T, vector<int> D) { n2 = N; for(int i = 1; i < N; i++) answer2[i] = oo; for(int i = 0; i < B; i++){ Adj2[S[i]].pb({T[i], D[i]}); Adj2[T[i]].pb({S[i], D[i]}); } for(auto it : Adj2[0]){ int v = it.fi, w = it.se; if(answer2[v] > answer2[0] + w){ answer2[v] = answer2[0] + w; pq2.push({answer2[v], v}); } } done2[0] = 1; lstt = 0, phasee = 0, remm = 9, nodee = (pq2.empty() ? 2047 : pq2.top().se), plss = (pq2.empty() ? 511 : pq2.top().fi); } //bool done2[N]; void send2(int x, int bits){ // cout << "SEND " << x << "\n"; for(int i = 0; i < bits; i++){ SendB((x & (1LL << (bits - i - 1))) != 0); } } void ReceiveB(bool y) { remm--; if(!phasee) aa = aa * 2 + y; else bb = bb * 2 + y; if(remm) return; if(!phasee){ // cout << "COMPARING " << aa << " " << plss << "\n"; send2(plss, 9); if(plss <= aa){ send2(nodee, 11); phasee = 0, remm = 9; } else{ phasee = 1, remm = 11; return; } } if(plss <= aa) bb = nodee; aa = min(aa, plss); lstt += aa; answer2[bb] = lstt; done2[bb] = 1; for(auto it : Adj2[bb]){ int v = it.fi, w = it.se; if(answer2[v] > answer2[bb] + w){ answer2[v] = answer2[bb] + w; pq2.push({answer2[v], v}); } } // lstt = aa = bb = 0; phasee = 0; plss = 511, nodee = 2047; while(!pq2.empty()){ int u = pq2.top().se, d = pq2.top().fi; // pq2.pop(); if(done2[u]){ pq2.pop(); continue; } //send1(d - lst, 9); plss = d - lstt; phasee = 0; remm = 9; nodee = u; break; } // cout << "CAN B " << lstt << " " << nodee << " " << plss << "\n"; }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...