Submission #948585

#	Time	Username	Problem	Language	Result	Execution time	Memory
948585		onepunchac168	City Mapping (NOI18_citymapping)	C++14	100 / 100	9 ms	864 KiB

citymapping

#include "citymapping.h"
#include <bits/stdc++.h>
using namespace std;
const int N=1e3+5;

int n;
#define ll long long
#define pb push_back
#define fi first
#define se second
typedef pair <ll,ll> ii;
ll dist[N];
ll par[N];
ll query(int u,int v)
{
    return get_distance(u,v);
}
vector <ll> vt[N];
ll sz[N];
bool fee[N];
void dfs(int u,int vv)
{
    sz[u]=1;
    for (auto v:vt[u])
    {
        if (v==vv)
        {
            continue;
        }
        dfs(v,u);
        sz[u]+=sz[v];
    }
}
void find_roads(int NN, int Q, int A[], int B[], int W[]) {
    n=NN;
    for (int i=1;i<=n;i++)
    {
        vt[i].clear();
    }
    dist[1]=0;
    ll dem=0;
    vector <ii> target;
    for (int i=2;i<=n;i++)
    {
        dist[i]=query(1,i);
        target.pb({dist[i],i});
    }
    sort (target.begin(),target.end());
    for (auto v:target)
    {
        dfs(1,-1);
        int root=1;
        int pref=-1;
        for (int i=1;i<=n;i++)
        {
            fee[i]=0;
        }
        fee[1]=1;
        while (true)
        {
            ll aa=root;
            while (true)
            {
                int child=-1;
                for (auto v:vt[root])
                {
                    if (v==pref||fee[v]==1)
                    {
                        continue;
                    }
                    if (child==-1||sz[child]<sz[v])
                    {
                        child=v;
                    }
                }
                if (child==-1)
                {
                    break;
                }
                pref=root;
                root=child;
                fee[root]=1;
            }
            if (root==aa)
            {
                vt[aa].pb(v.se);
                A[dem]=aa;
                B[dem]=v.se;
                W[dem]=dist[v.se]-dist[aa];
                dem++;
                vt[v.se].pb(aa);
                par[v.se]=aa;
                break;
            }
            ll a1=query(v.se,root);
            ll ds=(dist[v.se]+dist[root]-a1)/2;
            while (dist[root]!=ds)
            {
                root=par[root];
            }
            pref=par[root];
        }
    }

}

• Subtask 1: 9 / 9
• Subtask 2: 16 / 16
• Subtask 3: 13 / 13
• Subtask 4: 19 / 19
• Subtask 5: 43 / 43