oj.uz

Submission #948585

# Submission time Handle Problem Language Result Execution time Memory
948585 2024-03-18T08:03:58 Z onepunchac168 City Mapping (NOI18_citymapping) C++14
100 / 100
 9 ms 864 KB 
#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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 600 KB Correct: 2691 out of 500000 queries used.
2 Correct 6 ms 856 KB Correct: 2421 out of 500000 queries used.
3 Correct 5 ms 520 KB Correct: 4517 out of 500000 queries used.
4 Correct 4 ms 604 KB Correct: 5567 out of 500000 queries used.
5 Correct 6 ms 604 KB Correct: 3387 out of 500000 queries used.

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 600 KB Correct: 2691 out of 500000 queries used.
2 Correct 6 ms 856 KB Correct: 2421 out of 500000 queries used.
3 Correct 5 ms 520 KB Correct: 4517 out of 500000 queries used.
4 Correct 4 ms 604 KB Correct: 5567 out of 500000 queries used.
5 Correct 6 ms 604 KB Correct: 3387 out of 500000 queries used.
6 Correct 8 ms 604 KB Correct: 2009 out of 500000 queries used.
7 Correct 8 ms 604 KB Correct: 2063 out of 500000 queries used.
8 Correct 5 ms 604 KB Correct: 4244 out of 500000 queries used.
9 Correct 5 ms 672 KB Correct: 5089 out of 500000 queries used.
10 Correct 6 ms 852 KB Correct: 3054 out of 500000 queries used.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 604 KB Correct: 2086 out of 12000 queries used.
2 Correct 8 ms 604 KB Correct: 2304 out of 12000 queries used.
3 Correct 8 ms 604 KB Correct: 2457 out of 12000 queries used.
4 Correct 8 ms 856 KB Correct: 2470 out of 12000 queries used.
5 Correct 8 ms 604 KB Correct: 2240 out of 12000 queries used.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 604 KB Correct: 2086 out of 12000 queries used.
2 Correct 8 ms 604 KB Correct: 2304 out of 12000 queries used.
3 Correct 8 ms 604 KB Correct: 2457 out of 12000 queries used.
4 Correct 8 ms 856 KB Correct: 2470 out of 12000 queries used.
5 Correct 8 ms 604 KB Correct: 2240 out of 12000 queries used.
6 Correct 8 ms 604 KB Correct: 2473 out of 12000 queries used.
7 Correct 8 ms 604 KB Correct: 2382 out of 12000 queries used.
8 Correct 8 ms 604 KB Correct: 2207 out of 12000 queries used.
9 Correct 7 ms 600 KB Correct: 2235 out of 12000 queries used.
10 Correct 8 ms 604 KB Correct: 2302 out of 12000 queries used.

Subtask #5
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 600 KB Correct: 2691 out of 500000 queries used.
2 Correct 6 ms 856 KB Correct: 2421 out of 500000 queries used.
3 Correct 5 ms 520 KB Correct: 4517 out of 500000 queries used.
4 Correct 4 ms 604 KB Correct: 5567 out of 500000 queries used.
5 Correct 6 ms 604 KB Correct: 3387 out of 500000 queries used.
6 Correct 8 ms 604 KB Correct: 2009 out of 500000 queries used.
7 Correct 8 ms 604 KB Correct: 2063 out of 500000 queries used.
8 Correct 5 ms 604 KB Correct: 4244 out of 500000 queries used.
9 Correct 5 ms 672 KB Correct: 5089 out of 500000 queries used.
10 Correct 6 ms 852 KB Correct: 3054 out of 500000 queries used.
11 Correct 7 ms 604 KB Correct: 2086 out of 12000 queries used.
12 Correct 8 ms 604 KB Correct: 2304 out of 12000 queries used.
13 Correct 8 ms 604 KB Correct: 2457 out of 12000 queries used.
14 Correct 8 ms 856 KB Correct: 2470 out of 12000 queries used.
15 Correct 8 ms 604 KB Correct: 2240 out of 12000 queries used.
16 Correct 8 ms 604 KB Correct: 2473 out of 12000 queries used.
17 Correct 8 ms 604 KB Correct: 2382 out of 12000 queries used.
18 Correct 8 ms 604 KB Correct: 2207 out of 12000 queries used.
19 Correct 7 ms 600 KB Correct: 2235 out of 12000 queries used.
20 Correct 8 ms 604 KB Correct: 2302 out of 12000 queries used.
21 Correct 8 ms 604 KB Correct: 2502 out of 25000 queries used.
22 Correct 7 ms 864 KB Correct: 2071 out of 25000 queries used.
23 Correct 7 ms 604 KB Correct: 2284 out of 25000 queries used.
24 Correct 9 ms 688 KB Correct: 2036 out of 25000 queries used.
25 Correct 5 ms 604 KB Correct: 4436 out of 25000 queries used.
26 Correct 5 ms 600 KB Correct: 4358 out of 25000 queries used.
27 Correct 5 ms 604 KB Correct: 4307 out of 25000 queries used.
28 Correct 5 ms 604 KB Correct: 4417 out of 25000 queries used.
29 Correct 5 ms 604 KB Correct: 4502 out of 25000 queries used.
30 Correct 5 ms 604 KB Correct: 4442 out of 25000 queries used.
31 Correct 5 ms 604 KB Correct: 5151 out of 25000 queries used.
32 Correct 8 ms 604 KB Correct: 2223 out of 25000 queries used.
33 Correct 4 ms 604 KB Correct: 5083 out of 25000 queries used.
34 Correct 5 ms 604 KB Correct: 5158 out of 25000 queries used.
35 Correct 5 ms 656 KB Correct: 5100 out of 25000 queries used.
36 Correct 5 ms 604 KB Correct: 5118 out of 25000 queries used.
37 Correct 6 ms 604 KB Correct: 5144 out of 25000 queries used.
38 Correct 5 ms 600 KB Correct: 5102 out of 25000 queries used.
39 Correct 5 ms 604 KB Correct: 5135 out of 25000 queries used.
40 Correct 5 ms 656 KB Correct: 5168 out of 25000 queries used.
41 Correct 5 ms 604 KB Correct: 5124 out of 25000 queries used.
42 Correct 5 ms 604 KB Correct: 5203 out of 25000 queries used.
43 Correct 8 ms 604 KB Correct: 2087 out of 25000 queries used.
44 Correct 5 ms 600 KB Correct: 5116 out of 25000 queries used.
45 Correct 5 ms 600 KB Correct: 5090 out of 25000 queries used.
46 Correct 5 ms 604 KB Correct: 5068 out of 25000 queries used.
47 Correct 5 ms 600 KB Correct: 5179 out of 25000 queries used.
48 Correct 5 ms 600 KB Correct: 5135 out of 25000 queries used.
49 Correct 4 ms 604 KB Correct: 5091 out of 25000 queries used.
50 Correct 5 ms 604 KB Correct: 5105 out of 25000 queries used.
51 Correct 6 ms 600 KB Correct: 5099 out of 25000 queries used.
52 Correct 5 ms 604 KB Correct: 5128 out of 25000 queries used.
53 Correct 5 ms 600 KB Correct: 5144 out of 25000 queries used.
54 Correct 7 ms 604 KB Correct: 2333 out of 25000 queries used.
55 Correct 5 ms 604 KB Correct: 5196 out of 25000 queries used.
56 Correct 4 ms 684 KB Correct: 5141 out of 25000 queries used.
57 Correct 5 ms 604 KB Correct: 5125 out of 25000 queries used.
58 Correct 5 ms 656 KB Correct: 5115 out of 25000 queries used.
59 Correct 5 ms 604 KB Correct: 5104 out of 25000 queries used.
60 Correct 7 ms 600 KB Correct: 3041 out of 25000 queries used.
61 Correct 6 ms 856 KB Correct: 3317 out of 25000 queries used.
62 Correct 6 ms 604 KB Correct: 2917 out of 25000 queries used.
63 Correct 6 ms 604 KB Correct: 3317 out of 25000 queries used.
64 Correct 6 ms 604 KB Correct: 3103 out of 25000 queries used.
65 Correct 8 ms 604 KB Correct: 2067 out of 25000 queries used.
66 Correct 6 ms 604 KB Correct: 3228 out of 25000 queries used.
67 Correct 9 ms 600 KB Correct: 2018 out of 25000 queries used.
68 Correct 7 ms 604 KB Correct: 2394 out of 25000 queries used.
69 Correct 8 ms 604 KB Correct: 2451 out of 25000 queries used.
70 Correct 7 ms 604 KB Correct: 2414 out of 25000 queries used.