Submission #963995

#	Time	Username	Problem	Language	Result	Execution time	Memory
963995		12345678	City Mapping (NOI18_citymapping)	C++17	22 / 100	2082 ms	1240 KiB

citymapping

#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[]) {
    vector<pair<int, int>> k;
    for (int i=2; i<=N; i++) k.push_back({query(1, i), i});
    sort(k.begin(), k.end());
	for (int i=2; i<=N; i++)
    {
        rt=1;
        for (int j=1; j<=N; 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, k[i-2].second)+query(1, u)==query(1, k[i-2].second)) rt=u;
            else used[u]=1;
        }
        A[i-2]=k[i-2].second;
        B[i-2]=rt;
        d[rt].push_back(k[i-2].second);
        //cout<<"edge "<<i<<' '<<rt<<'\n';
        W[i-2]=query(rt, k[i-2].second);
    }
}
/*
6 100 1
1 6 3
1 5 4
6 3 9
6 2 5
2 4 10
*/

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