Submission #423013

#TimeUsernameProblemLanguageResultExecution timeMemory
423013two_sidesTwo Transportations (JOI19_transportations)C++17
70 / 100
751 ms48804 KiB
#include "Azer.h" #include <bits/stdc++.h> using namespace std; mt19937 rng(chrono::high_resolution_clock ::now().time_since_epoch().count()); namespace { template <class X, class Y> bool cmin(X &a, const Y &b) { return a > b ? a = b, 1 : 0; } const int MAXN = 2005; struct edge { int v, w; edge(int v, int w): v(v), w(w) {} bool operator < (const edge &o) const { return w > o.w; } }; int N, last; bool coin; int cnt, cur, prv, relaxed; vector<vector<edge>> adj; vector<int> dis; vector<char> vis; priority_queue<edge> pq; void SendA1(int x, int k) { while (k--) SendA(bool(x >> k & 1)); } void Relax(int u) { last = dis[u]; vis[u] = true; for (edge e : adj[u]) if (cmin(dis[e.v], dis[u] + e.w)) pq.emplace(e.v, dis[e.v]); while (pq.size()) { auto p = pq.top(); if (dis[p.v] < p.w || vis[p.v]) pq.pop(); else break; } relaxed++; } void NewPhase() { if (relaxed == N) return; coin = 1; SendA(coin ^ 1); if (coin) { if (pq.size()) SendA1(pq.top().w - last, 9); else SendA1(511, 9); } cnt = cur = prv = 0; } } void InitA(int N, int A, vector<int> U, vector<int> V, vector<int> C) { ::N = N; relaxed = 0; dis.assign(N, 1e9); adj.assign(N, vector <edge> ()); vis.assign(N, 0); for (int i = 0; i < U.size(); i++) { adj[U[i]].emplace_back(V[i], C[i]); adj[V[i]].emplace_back(U[i], C[i]); } pq.emplace(0, dis[0] = 0); Relax(0); NewPhase(); } void ReceiveA(bool x) { cur = (cur << 1) | x; if (coin) { if (++cnt == 1) { if (x) { SendA1(pq.top().v, 11); Relax(pq.top().v); NewPhase(); } } else if (cnt == 10) { prv = cur; cur = 0; } else if (cnt == 21) { dis[cur] = last + prv; Relax(cur); NewPhase(); } } else { if (++cnt == 9) { if (pq.size() && cur + last > pq.top().w) { SendA(0); SendA1(pq.top().w - last, 9); SendA1(pq.top().v, 11); Relax(pq.top().v); NewPhase(); } else { prv = cur; cur = 0; SendA(1); } } else if (cnt == 20) { dis[cur] = last + prv; Relax(cur); NewPhase(); } } } vector<int> Answer() { return dis; }
#include "Baijan.h" #include <bits/stdc++.h> using namespace std; namespace { template <class X, class Y> bool cmin(X &a, const Y &b) { return a > b ? a = b, 1 : 0; } const int MAXN = 2005; struct edge { int v, w; edge(int v, int w): v(v), w(w) {} bool operator < (const edge &o) const { return w > o.w; } }; int N, last; bool coin; int cnt, cur, prv; vector<vector<edge>> adj; vector<int> dis; vector<char> vis; priority_queue<edge> pq; void SendB1(int x, int k) { while (k--) SendB(bool(x >> k & 1)); } void Relax(int u) { last = dis[u]; vis[u] = true; for (edge e : adj[u]) if (cmin(dis[e.v], dis[u] + e.w)) pq.emplace(e.v, dis[e.v]); while (pq.size()) { auto p = pq.top(); if (dis[p.v] < p.w || vis[p.v]) pq.pop(); else break; } } void NewPhase() { cnt = cur = prv = 0; } } void InitB(int N, int B, vector<int> S, vector<int> T, vector<int> D) { ::N = N; dis.assign(N, 1e9); adj.assign(N, vector <edge> ()); vis.assign(N, 0); for (int i = 0; i < S.size(); i++) { adj[S[i]].emplace_back(T[i], D[i]); adj[T[i]].emplace_back(S[i], D[i]); } pq.emplace(0, dis[0] = 0); Relax(0); NewPhase(); } void ReceiveB(bool y) { if (++cnt == 1) { coin = y; if (y) { if (pq.size()) SendB1(pq.top().w - last, 9); else SendB1(511, 9); } return; } cur = (cur << 1) | y; if (coin) { if (cnt == 2) { if (cur) { SendB1(pq.top().v, 11); Relax(pq.top().v); NewPhase(); } } else if (cnt == 11) { prv = cur; cur = 0; } else if (cnt == 22) { dis[cur] = last + prv; Relax(cur); NewPhase(); } } else { if (cnt == 10) { if (pq.size() && cur + last > pq.top().w) { SendB(0); SendB1(pq.top().w - last, 9); SendB1(pq.top().v, 11); Relax(pq.top().v); NewPhase(); } else { prv = cur; cur = 0; SendB(1); } } else if (cnt == 21) { dis[cur] = last + prv; Relax(cur); NewPhase(); } } }

Compilation message (stderr)

Azer.cpp: In function 'void InitA(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
Azer.cpp:71:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     for (int i = 0; i < U.size(); i++) {
      |                     ~~^~~~~~~~~~

Baijan.cpp: In function 'void InitB(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
Baijan.cpp:59:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for (int i = 0; i < S.size(); i++) {
      |                     ~~^~~~~~~~~~
#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...