oj.uz

Submission #963995

# Submission time Handle Problem Language Result Execution time Memory
963995 2024-04-16T07:27:58 Z 12345678 City Mapping (NOI18_citymapping) C++17
22 / 100
 2000 ms 1240 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<=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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 1012 KB Correct: 8475 out of 500000 queries used.
2 Correct 14 ms 1156 KB Correct: 9386 out of 500000 queries used.
3 Correct 14 ms 1044 KB Correct: 10135 out of 500000 queries used.
4 Correct 14 ms 1116 KB Correct: 10148 out of 500000 queries used.
5 Correct 18 ms 1240 KB Correct: 9037 out of 500000 queries used.

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 1012 KB Correct: 8475 out of 500000 queries used.
2 Correct 14 ms 1156 KB Correct: 9386 out of 500000 queries used.
3 Correct 14 ms 1044 KB Correct: 10135 out of 500000 queries used.
4 Correct 14 ms 1116 KB Correct: 10148 out of 500000 queries used.
5 Correct 18 ms 1240 KB Correct: 9037 out of 500000 queries used.
6 Execution timed out 2082 ms 556 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 1036 KB Correct: 8392 out of 12000 queries used.
2 Correct 17 ms 1176 KB Correct: 8415 out of 12000 queries used.
3 Correct 17 ms 1120 KB Correct: 8485 out of 12000 queries used.
4 Correct 17 ms 1116 KB Correct: 8415 out of 12000 queries used.
5 Correct 16 ms 1112 KB Correct: 8395 out of 12000 queries used.

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 1036 KB Correct: 8392 out of 12000 queries used.
2 Correct 17 ms 1176 KB Correct: 8415 out of 12000 queries used.
3 Correct 17 ms 1120 KB Correct: 8485 out of 12000 queries used.
4 Correct 17 ms 1116 KB Correct: 8415 out of 12000 queries used.
5 Correct 16 ms 1112 KB Correct: 8395 out of 12000 queries used.
6 Execution timed out 2067 ms 512 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 1012 KB Correct: 8475 out of 500000 queries used.
2 Correct 14 ms 1156 KB Correct: 9386 out of 500000 queries used.
3 Correct 14 ms 1044 KB Correct: 10135 out of 500000 queries used.
4 Correct 14 ms 1116 KB Correct: 10148 out of 500000 queries used.
5 Correct 18 ms 1240 KB Correct: 9037 out of 500000 queries used.
6 Execution timed out 2082 ms 556 KB Time limit exceeded
7 Halted 0 ms 0 KB -