Submission #961824

#TimeUsernameProblemLanguageResultExecution timeMemory
961824Der_VlaposCity Mapping (NOI18_citymapping)C++17
22 / 100
25 ms856 KiB
#include "citymapping.h" #include <bits/stdc++.h> namespace operators { template <typename T1, typename T2> std::istream &operator>>(std::istream &in, std::pair<T1, T2> &x) { in >> x.first >> x.second; return in; } template <typename T1, typename T2> std::ostream &operator<<(std::ostream &out, std::pair<T1, T2> x) { out << x.first << " " << x.second; return out; } template <typename T1> std::istream &operator>>(std::istream &in, std::vector<T1> &x) { for (auto &i : x) in >> i; return in; } template <typename T1> std::ostream &operator<<(std::ostream &out, std::vector<T1> &x) { for (auto &i : x) out << i << " "; return out; } template <typename T1> std::ostream &operator<<(std::ostream &out, std::set<T1> &x) { for (auto &i : x) out << i << " "; return out; } template <typename T1> std::ostream &operator<<(std::ostream &out, std::multiset<T1> &x) { for (auto &i : x) out << i << " "; return out; } } // name spaces using namespace std; using namespace operators; // end of name spaces // defines #define ll long long #define ull unsigned long long #define pb push_back #define mp make_pair #define pii pair<int, int> #define pll pair<ll, ll> #define f first #define s second #define uint unsigned int #define all(vc) vc.begin(), vc.end() // end of defines vector<vector<int>> tree; vector<pair<pll, ll>> edges; vector<ll> D, sz; void dfs(int v) { sz[v] = 1; for (auto tov : tree[v]) { dfs(tov); sz[v] += sz[tov]; } } void find_roads(int N, int Q, int A[], int B[], int W[]) { tree.resize(N); D.resize(N); sz.resize(N); vector<pii> target; for (ll i = 1; i < N; ++i) { D[i] = (ll)get_distance(1, i + 1); target.pb({D[i], i}); sort(all(target)); } int i = 0; vector<int> pr(N); for (auto [d, v] : target) { vector<int> used(N, 0); dfs(0); int root = 0; used[root] = 1; while (true) { int bf = root; while (true) { int to = -1; for (auto tov : tree[root]) if (!used[tov] and (to == -1 or sz[to] < sz[tov])) to = tov; if (to == -1) break; root = to; used[root] = 1; } if (root == bf) { tree[root].pb(v); A[i] = v + 1; B[i] = root + 1; W[i] = D[v] - D[root]; pr[v] = root; ++i; break; } int D1 = get_distance(root + 1, v + 1); int upTo = D1 - ((D1 + D[v] - D[root]) / 2); if (D[v] == D[root] + D1) continue; while (upTo > 0 and root) { upTo -= D[root] - D[pr[root]]; if (upTo >= 0) root = pr[root]; } } } return; } // //////////////////////////////////////////////////////// // // #include "citymapping.h" // #include <bits/stdc++.h> // using namespace std; // static int N, Q, S, twok[1005][11], depth[1005], curQ, target = 6500; // static long long dist[1005]; // static vector<pair<int, int>> adjlist[1005]; // static vector<pair<pair<int, int>, int>> edgelist, user_edgelist; // static void dfs(int x, int p, long long d, int dep) // { // dist[x] = d; // depth[x] = dep; // twok[x][0] = p; // for (int i = 1; i <= 10; i++) // { // if (twok[x][i - 1] == -1) // break; // twok[x][i] = twok[twok[x][i - 1]][i - 1]; // } // for (int i = 0; i < (int)adjlist[x].size(); i++) // { // if (adjlist[x][i].first == p) // continue; // dfs(adjlist[x][i].first, x, d + adjlist[x][i].second, dep + 1); // } // } // static int lca(int x, int y) // { // if (depth[x] > depth[y]) // swap(x, y); // int dd = depth[y] - depth[x]; // for (int i = 0; i <= 10; i++) // if (dd & (1 << i)) // y = twok[y][i]; // if (x == y) // return x; // for (int i = 10; i >= 0; i--) // { // if (twok[x][i] != twok[y][i]) // { // x = twok[x][i]; // y = twok[y][i]; // } // } // return twok[x][0]; // } // long long get_distance(int X, int Y) // { // if (X <= 0 || X > N || Y <= 0 || Y > N) // { // printf("Wrong Answer: get_distance() arguments out of range.\n"); // exit(0); // } // curQ++; // if (curQ > Q) // { // printf("Wrong Answer: Too many calls to get_distance().\n"); // exit(0); // } // return dist[X - 1] + dist[Y - 1] - dist[lca(X - 1, Y - 1)] * 2; // } // int main() // { // if (scanf("%d%d%d", &N, &Q, &S) != 3) // { // printf("Wrong Input Format\n"); // exit(0); // } // for (int i = 0; i < N - 1; i++) // { // int a, b, w; // if (scanf("%d%d%d", &a, &b, &w) != 3) // { // printf("Wrong Input Format\n"); // return 0; // } // a--; // b--; // adjlist[a].push_back(make_pair(b, w)); // adjlist[b].push_back(make_pair(a, w)); // edgelist.push_back(make_pair(make_pair(min(a, b) + 1, max(a, b) + 1), w)); // } // sort(edgelist.begin(), edgelist.end()); // memset(twok, -1, sizeof(twok)); // dfs(0, -1, 0, 0); // int A[N - 1], B[N - 1], W[N - 1]; // memset(A, 0, sizeof(A)); // memset(B, 0, sizeof(B)); // memset(W, 0, sizeof(W)); // find_roads(N, Q, A, B, W); // for (int i = 0; i < N - 1; i++) // { // user_edgelist.push_back(make_pair(make_pair(min(A[i], B[i]), max(A[i], B[i])), W[i])); // } // sort(user_edgelist.begin(), user_edgelist.end()); // if (edgelist != user_edgelist) // { // printf("Wrong Answer: Reported list of edges differ from actual.\n"); // exit(0); // } // cout << "Correct"; // exit(0); // if (S <= 4) // { // printf("Score: 100.00%%\nCorrect: %d out of %d queries used.\n", curQ, Q); // exit(0); // } // else // { // if (curQ <= target) // printf("Score: 100.00%%\nCorrect: %d out of %d queries used.\n", curQ, Q); // else if (curQ >= 12000) // printf("Score: %.2lf%%\nCorrect: %d out of %d queries used.\n", (10.0 - 10.0 * ((double)(curQ - 12000) / 13000)) / 43 * 100, curQ, Q); // else // printf("Score: %.2lf%%\nCorrect: %d out of %d queries used.\n", (40.0 - 30.0 * ((double)(curQ - target) / (12000 - target))) / 43 * 100, curQ, Q); // } // }
#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...