제출 #283031

#제출 시각아이디문제언어결과실행 시간메모리
283031rama_pangSnowy Roads (JOI16_snowy)C++14
100 / 100
63 ms2644 KiB
#include "Anyalib.h" #include <bits/stdc++.h> using namespace std; namespace { int N; vector<int> A, B; map<pair<int, int>, int> name; vector<int> depth; vector<vector<int>> adj; vector<pair<int, int>> euler; void Dfs(int u, int p) { euler.emplace_back(p, u); for (auto v : adj[u]) if (v != p) { depth[v] = depth[u] + 1; Dfs(v, u); } euler.emplace_back(u, p); } void Init(int N, vector<int> A, vector<int> B) { ::N = N, ::A = A, ::B = B; adj.resize(N); depth.resize(N); for (int i = 0; i + 1 < N; i++) { adj[A[i]].emplace_back(B[i]); adj[B[i]].emplace_back(A[i]); name[{A[i], B[i]}] = name[{B[i], A[i]}] = i; } Dfs(0, -1); } } void InitAnya(int N , int A[] , int B[]) { Init(N, vector<int>(A, A + N - 1), vector<int>(B, B + N - 1)); } void Anya(int C[]) { vector<int> sum(1001); for (int i = 0; i <= 1000; i++) { if (i > 0) { sum[i] = sum[i - 1]; } if (i < (int) euler.size()) { int u = euler[i].first, v = euler[i].second; int id = name[{u, v}]; if (u == -1 || v == -1) { continue; } if (depth[u] < depth[v]) { sum[i] += C[id]; } else { sum[i] -= C[id]; } } } int ptr = 0; for (int i = 0; i + 1 < N; i++) { Save(ptr++, C[i]); } for(int i = 0; i <= 1000; i += 20) { for (int j = 0; j < 9; j++) { if (sum[i] & (1 << j)) { Save(ptr++, 1); } else { Save(ptr++, 0); } } } }
#include "Borislib.h" #include <bits/stdc++.h> using namespace std; namespace { int N; vector<int> A, B; map<pair<int, int>, int> name; vector<int> depth; vector<vector<int>> adj; vector<pair<int, int>> euler; void Dfs(int u, int p) { euler.emplace_back(p, u); for (auto v : adj[u]) if (v != p) { depth[v] = depth[u] + 1; Dfs(v, u); } euler.emplace_back(u, p); } void Init(int N, vector<int> A, vector<int> B) { ::N = N, ::A = A, ::B = B; adj.resize(N); depth.resize(N); for (int i = 0; i + 1 < N; i++) { adj[A[i]].emplace_back(B[i]); adj[B[i]].emplace_back(A[i]); name[{A[i], B[i]}] = name[{B[i], A[i]}] = i; } Dfs(0, -1); } } void InitBoris(int N , int A[] , int B[]) { Init(N, vector<int>(A, A + N - 1), vector<int>(B, B + N - 1)); } int Boris(int city) { if (city == 0) { return 0; } int where = -1; for (int i = 0; i < (int) euler.size(); i++) { if (euler[i].second == city) { where = i; break; } } assert(where != -1); vector<int> savepos(1001, -1); int ptr = 0; for (int i = 0; i + 1 < N; i++) { ptr += 1; } for(int i = 0; i <= 1000; i += 20) { savepos[i] = ptr; for (int j = 0; j < 9; j++) { ptr += 1; } } int ans = 0, loc = -1; for (int cnt = 0;; cnt++) { if (savepos[where + cnt] != -1) { for (int j = where + 1; j <= where + cnt; j++) { if (j < (int) euler.size()) { int u = euler[j].first, v = euler[j].second; if (u == -1 || v == -1) { continue; } if (depth[u] < depth[v]) { ans -= Ask(name[{euler[j].first, euler[j].second}]); } else { ans += Ask(name[{euler[j].first, euler[j].second}]); } } } loc = where + cnt; break; } if (savepos[where - cnt] != -1) { for (int j = where; j > where - cnt; j--) { if (j < (int) euler.size()) { int u = euler[j].first, v = euler[j].second; if (u == -1 || v == -1) { continue; } if (depth[u] < depth[v]) { ans += Ask(name[{euler[j].first, euler[j].second}]); } else { ans -= Ask(name[{euler[j].first, euler[j].second}]); } } } loc = where - cnt; break; } } assert(loc != -1 && savepos[loc] != -1); for (int j = 0; j < 9; j++) { if (Ask(savepos[loc] + j)) { ans += 1 << j; } } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...