oj.uz

Submission #963994

# Submission time Handle Problem Language Result Execution time Memory
963994 2024-04-16T07:21:54 Z 12345678 City Mapping (NOI18_citymapping) C++17
0 / 100
 2000 ms 1116 KB 
#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<=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, 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);
    }
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2055 ms 604 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2055 ms 604 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 1116 KB Reported list of edges differ from actual.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 1116 KB Reported list of edges differ from actual.
2 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2055 ms 604 KB Time limit exceeded
2 Halted 0 ms 0 KB -