oj.uz

Submission #963906

# Submission time Handle Problem Language Result Execution time Memory
963906 2024-04-16T02:46:41 Z 12345678 City Mapping (NOI18_citymapping) C++17
0 / 100
 2000 ms 600 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[]) {
	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, i)+query(1, u)==query(1, i)) rt=u;
            else used[u]=1;
        }
        A[i-2]=i;
        B[i-2]=rt;
        d[rt].push_back(i);
        //cout<<"edge "<<i<<' '<<rt<<'\n';
        W[i-2]=query(rt, i);
    }
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2041 ms 600 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 2041 ms 600 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

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

Subtask #4
0 / 19.0

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

Subtask #5
0 / 43.0

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