| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 939144 | winter0101 | City Mapping (NOI18_citymapping) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
//#include "citymapping.h"
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
#define pil pair<int,long long>
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;
}
vector<pii>aaa[1009];
mt19937_64 rng(101094);
long long d[1009][1009];
long long ask(int x,int y){
if (d[x][y]!=-1)return d[x][y];
return d[x][y]=d[y][x]=get_distance(x,y);
}
bool add[1009];
vector<int>xd[1009];
void solve(vector<int>&tmp){
if (sz(tmp)<=1)return;
shuffle(all(tmp),rng);
for (auto v:tmp)add[v]=0;
shuffle(all(tmp),rng);
int s=tmp[0],t=tmp.back();
ask(s,t);
vector<int>vertice;
for (auto v:tmp){
if (ask(s,v)+ask(t,v)==ask(s,t)){
vertice.pb(v);
add[v]=1;
}
}
//cout<<s<<" "<<t<<'\n';
sort(all(vertice),[&](int i,int j){
return ask(s,i)<ask(s,j);
});
auto add_edg=[&](int u,int v,int w){
aaa[u].pb({v,w});
aaa[v].pb({u,w});
//cerr<<u<<" "<<v<<" "<<w<<'\n';
return;
};
for1(i,1,sz(vertice)-1){
add_edg(vertice[i],vertice[i-1],ask(vertice[i],s)-ask(vertice[i-1],s));
}
for(auto v:tmp){
if (add[v])continue;
for (auto u:vertice){
if (ask(s,v)-ask(s,u)==ask(t,v)-ask(t,u)&&ask(s,v)>ask(s,u)){
xd[u].pb(v);
//cerr<<u<<" "<<v<<'\n';
}
}
}
for (auto u:vertice){
if (!xd[u].empty()){
if ((u!=s&&u!=t)||sz(aaa[u])>=2){
vector<int>cop;
cop.swap(xd[u]);
int mn=cop[0];
for (auto v:cop){
if (ask(s,v)<ask(s,mn)){
mn=v;
}
}
add_edg(u,mn,ask(s,mn)-ask(s,u));
solve(cop);
}
else {
sort(all(xd[u]),[&](int i,int j){
return ask(s,i)<ask(s,j);
});
vector<int>lft,rht;
lft.pb(xd[u][0]);
for (auto v:xd[u]){
if (v==xd[u][0])continue;
if (ask(xd[u][0],s)+ask(xd[u][0],v)==ask(s,v)){
lft.pb(v);
}
else {
rht.pb(v);
}
}
if (!lft.empty())add_edg(u,lft[0],ask(s,lft[0])-ask(s,u));
if (!rht.empty())add_edg(u,rht[0],ask(s,rht[0])-ask(s,u));
xd[u].clear();
solve(lft),solve(rht);
}
}
}
}
void find_roads(int N, int Q, int A[], int B[], int W[]) {
for1(i,1,N){
for1(j,1,N){
d[i][j]=-1;
}
d[i][i]=0;
}
vector<int>tree;
for1(i,1,N)tree.pb(i);
solve(tree);
int cnt=0;
for1(i,1,N){
for (auto v:aaa[i]){
if (v.fi>i){
A[cnt]=v.fi,B[cnt]=i,W[cnt]=v.se;
cnt++;
}
}
}
}
int A[1009],B[1009],W[1009];
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
freopen("temp.INP","r",stdin);
freopen("temp.OUT","w",stdout);
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);
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);
}
/*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);
}*/
cout<<"AC";
exit(0);
}