Submission #132107

#TimeUsernameProblemLanguageResultExecution timeMemory
132107ekremTwo Transportations (JOI19_transportations)C++14
0 / 100
3000 ms992 KiB
#include "Azer.h" #include <bits/stdc++.h> #define st first #define nd second #define mp make_pair #define pb push_back #define sol (k+k) #define sag (k+k+1) #define orta ((bas+son)/2) #define coc g[node][i] #define mod 1000000007 #define inf 1000000009 #define MAXN 1000005 using namespace std; typedef long long ll; typedef pair < int , int > ii; typedef vector < int > vi; namespace { int n=0, m=0,su=0, crp = 1, node = -1, yol=0, say=0, onceki=0, of, d[MAXN], u[MAXN]; int cnt=0; ii mn; vi x, y, z; void yolla(int x, int y){ if(x < 0 or x >= (1<<y))assert(0); for(int i = 1; i <= y; i++){ SendA(x%2); x /= 2; } } } // namespace void InitA(int N, int A, vi U, vi V, vi W) { n = N;x = U;y = V;z = W;m = A; u[0] = 1; say++; for(int i = 1; i < n; i++) d[i] = inf; for(int i = 0; i < m; i++){ d[y[i]] = min(d[y[i]], d[x[i]] + z[i]); d[x[i]] = min(d[x[i]], d[y[i]] + z[i]); } mn = mp(510, 0); for(int i = 0; i < n; i++) if(!u[i]) mn = min(mn, mp(d[i] - onceki, i)); yolla(mn.nd, 11); yolla(mn.st, 9); } void ReceiveA(bool yy) { // cout << "A"<<yy << " " << cnt<<endl; ++cnt; su += crp*yy; crp *= 2; if(cnt == 11){ node = su; su = 0;crp = 1; cnt = 0; // cout << "Gectik" << endl; } if(cnt == 9 and node != -1){ // cout << onceki << " -> "; yol = onceki + ((su == 510)?inf:su); // cout << "A ya geldi " << node << " " << yol << endl; su = 0;crp = 1;cnt = 0; d[node] = min(d[node], yol); if(mn.st == 510)mn.st = inf; // cout << "Sonucumuz " << mn.st << " " << yol << endl; if(onceki + mn.st < yol){ onceki = onceki + mn.st; u[mn.nd] = 1; say++; } else{ onceki = yol; u[node] = 1; say++; } if(say >= n) return; node = -1; for(int i = 0; i < n; i++)if(!u[i])d[i] = inf; for(int i = 0; i < m; i++){ d[y[i]] = min(d[y[i]], d[x[i]] + z[i]); d[x[i]] = min(d[x[i]], d[y[i]] + z[i]); } mn = mp(510, 0); for(int i = 0; i < n; i++) if(!u[i]) mn = min(mn, mp(d[i] - onceki, i)); // cout << "A de buldum" << mn.nd << " " << d[mn.nd] << ", yolladim " << mn.st << " cunk " << onceki << endl; of = mn.nd; yolla(mn.nd, 11); yolla(mn.st, 9); // onceki = mn.st;//bura dogru mu emin degilim } } void sonsuz(int x){ sonsuz(x+x); } vi Answer() { vi ans(n); for (int k = 0; k < n; ++k){ if(d[k] >= inf)sonsuz(1); if(d[k] < 0)assert(0); ans[k] = d[k]; } return ans; }
#include "Baijan.h" #include <bits/stdc++.h> #define st first #define nd second #define mp make_pair #define pb push_back #define sol (k+k) #define sag (k+k+1) #define orta ((bas+son)/2) #define coc g[node][i] #define mod 1000000007 #define inf 1000000009 #define MAXN 1000005 using namespace std; typedef long long ll; typedef pair < int , int > ii; typedef vector < int > vi; namespace { int n = 0, m = 0, su = 0, crp = 1, node = -1, yol = 0, onceki = 0, d[MAXN], u[MAXN]; int cnt = 0; vi x, y, z; void yolla(int x, int y){ if(x < 0 or x >= (1<<y))assert(0); for(int i = 1; i <= y; i++){ SendB(x%2); x /= 2; } } } // namespace void InitB(int N, int B, vi S, vi T, vi D) { if(N > 1400)assert(0); n = N;m = B;x = S;y = T;z = D; u[0] = 1; for(int i = 0; i < n; i++)if(!u[i])d[i] = inf; } void ReceiveB(bool yy) { // cout << "B"<<yy << " " << cnt<<endl; ++cnt; su += crp*yy; crp *= 2; if(cnt == 11){ node = su; su = 0;crp = 1; cnt = 0; // cout << "Gectik" << endl; } if(cnt == 9 and node != -1){ // cout << onceki << " -> "; yol = onceki + ((su == 510)?inf:su); su = 0;crp = 1;cnt = 0; // cout << "B ya geldi " << node << " " << yol << endl; for(int i = 0; i < n; i++)if(!u[i])d[i] = inf; for(int i = 0; i < m; i++){ d[y[i]] = min(d[y[i]], d[x[i]] + z[i]); d[x[i]] = min(d[x[i]], d[y[i]] + z[i]); } ii mn = mp(510, 0); for(int i = 0; i < n; i++) if(!u[i]) mn = min(mn, mp(d[i] - onceki, i)); // cout << "B de buldum" << mn.nd << " " << d[mn.nd] << ", yolladim " << mn.st << " cunk " << onceki << endl; yolla(mn.nd, 11); yolla(mn.st, 9); d[node] = min(d[node], yol); if(mn.st == 510)mn.st = inf; // cout << "Sonucumuz " << onceki + mn.st << " " << yol << endl; if(onceki + mn.st < yol){ onceki = onceki + mn.st; u[mn.nd] = 1; } else{ onceki = yol; u[node] = 1; } // onceki = mn.st;//bura dogru mu emin degilim node = -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...
#Verdict Execution timeMemoryGrader output
Fetching results...