Submission #964022

#TimeUsernameProblemLanguageResultExecution timeMemory
96402212345678City Mapping (NOI18_citymapping)C++17
32 / 100
2021 ms1112 KiB
#include "citymapping.h" #include <bits/stdc++.h> using namespace std; #define ll long long const ll nx=1e3+5; ll ds[nx]; ll hv[nx], l[nx], sz[nx], rt, pa[nx], w[nx], t; vector<pair<ll, ll>> k; vector<ll> d[nx]; map<pair<ll, ll>, ll> mp; ll dfssz(ll u) { sz[u]=1; for (auto v:d[u]) sz[u]+=dfssz(v); if (d[u].size()==1) hv[u]=d[u][0], l[u]=-1; else if (d[u].size()==2) { if (sz[d[u][0]]<sz[d[u][1]]) swap(d[u][0], d[u][1]); hv[u]=d[u][0]; l[u]=d[u][1]; } return sz[u]; } ll query(ll u, ll 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[]) { rt=1; for (ll i=1; i<=N; i++) if (i!=rt) ds[i]=query(rt, i), k.push_back({ds[i], i}); sort(k.begin(), k.end()); for (auto [_, u]:k) { for (ll i=1; i<=N; i++) hv[i]=l[i]=-1; dfssz(rt); ll tmp=rt; while (1) { while (hv[tmp]!=-1) tmp=hv[tmp]; ll ld=query(rt, tmp)-((query(rt, tmp)+query(rt, u))-query(u, tmp))/2; while (ld!=0) ld-=w[tmp], tmp=pa[tmp]; if (d[tmp].size()<2) { d[tmp].push_back(u), pa[u]=tmp, w[u]=query(u, tmp), A[t]=u, B[t]=tmp, W[t++]=query(u, tmp); break; } else tmp=l[tmp]; } } }
#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...