Submission #963906

#TimeUsernameProblemLanguageResultExecution timeMemory
96390612345678City Mapping (NOI18_citymapping)C++17
0 / 100
2041 ms600 KiB
#include "citymapping.h" #include <bits/stdc++.h> using namespace std; #define ll long long const int nx=1e3+5; int rt, used[nx], sz[nx], u; map<pair<int, int>, ll> mp; vector<int> d[nx]; int dfssz(int u) { //cout<<"dfs "<<u<<'\n'; sz[u]=1; for (auto v:d[u]) if (!used[v]) sz[u]+=dfssz(v); return sz[u]; } int findcentroid(int u, int rtsz) { for (auto v:d[u]) if (!used[v]&&(2*sz[v]+2)>=rtsz) return findcentroid(v, rtsz); return u; } ll query(int u, int v) { if (u>v) swap(u, v); if (mp.find({u, v})!=mp.end()) return mp[{u, v}]; return mp[{u, v}]=get_distance(u, v); } void find_roads(int N, int Q, int A[], int B[], int W[]) { for (int i=2; i<=N; i++) { rt=1; for (int j=1; j<=i; j++) used[j]=0; while (dfssz(rt)!=1) { //printf("debug %d %d %d\n", i, rt, dfssz(rt)); u=findcentroid(rt, sz[rt]); if (query(u, i)+query(1, u)==query(1, i)) rt=u; else used[u]=1; } A[i-2]=i; B[i-2]=rt; d[rt].push_back(i); //cout<<"edge "<<i<<' '<<rt<<'\n'; W[i-2]=query(rt, 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...