oj.uz

Submission #941698

# Submission time Handle Problem Language Result Execution time Memory
941698 2024-03-09T09:58:14 Z abcvuitunggio City Mapping (NOI18_citymapping) C++17
100 / 100
 21 ms 8792 KB 
#include "citymapping.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;
struct edge{
    int a,b,w;
};
int d[1001][1001],h[1001],deg[1001];
vector <edge> res;
vector <pair <int, int>> tmp;
vector <int> ve[1001];
vector <pair <int, int>> ke[1001];
map <int, int> mp;
int get(int i, int j){
    if (i==j)
        return 0;
    if (i>j)
        swap(i,j);
    if (d[i][j])
        return d[i][j];
    return d[i][j]=get_distance(i,j);
}
void addEdge(int a, int b, int w){
    deg[a]++;
    deg[b]++;
    res.push_back({a,b,w});
}
void dfs(int u, int p, int root, int cur=0){
    d[root][u]=d[u][root]=cur;
    for (auto [v,w]:ke[u])
        if (v!=p)
            dfs(v,u,root,cur+w);
}
void solve(int x){
    sort(ve[x].begin(),ve[x].end(),[](int i, int j){return h[i]<h[j];});
    addEdge(x,ve[x][0],h[ve[x][0]]);
    for (int i=1;i<ve[x].size();i++){
        vector <pair <int, int>> c;
        int u=ve[x][i];
        for (int j=i-1;j>=0;j--)
            if (deg[ve[x][j]]<3&&h[u]>h[ve[x][j]])
                c.push_back({ve[x][j],h[u]-h[ve[x][j]]});
        while (c.size()>1){
            int val=get(c[0].first,u);
            vector <pair <int, int>> c2;
            for (auto [i,j]:c)
                if (get(c[0].first,i)+j==val)
                    c2.push_back({i,j});
            swap(c,c2);
        }
        auto [v,w]=c[0];
        addEdge(u,v,w);
        ke[u].push_back({v,w});
        ke[v].push_back({u,w});
        dfs(u,u,u);
    }
}
void find_roads(int32_t n, int32_t Q, int32_t A[], int32_t B[], int32_t W[]){
    int a=1,b=1,mx=0;
    for (int i=2;i<=n;i++)
        if (mx<get(1,i)){
            a=i;
            mx=get(1,i);
        }
    mx=0;
    for (int i=1;i<=n;i++)
        if (mx<get(a,i)){
            b=i;
            mx=get(a,i);
        }
    for (int i=1;i<=n;i++)
        if (get(a,i)+get(i,b)==get(a,b)){
            tmp.push_back({get(a,i),i});
            mp[get(a,i)]=i;
        }
    sort(tmp.begin(),tmp.end());
    for (int i=0;i+1<tmp.size();i++)
        addEdge(tmp[i].second,tmp[i+1].second,tmp[i+1].first-tmp[i].first);
    for (int i=1;i<=n;i++){
        int da=(get(a,b)+get(a,i)-get(b,i))/2;
        h[i]=(get(a,i)+get(b,i)-get(a,b))/2;
        if (mp[da]!=i)
            ve[mp[da]].push_back(i);
    }
    for (int i=1;i<=n;i++)
        if (!ve[i].empty())
            solve(i);
    for (int i=0;i<n-1;i++){
        A[i]=res[i].a;
        B[i]=res[i].b;
        W[i]=res[i].w;
    }
}

Compilation message

citymapping.cpp: In function 'void solve(long long int)':
citymapping.cpp:37:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for (int i=1;i<ve[x].size();i++){
      |                  ~^~~~~~~~~~~~~
citymapping.cpp: In function 'void find_roads(int32_t, int32_t, int32_t*, int32_t*, int32_t*)':
citymapping.cpp:77:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     for (int i=0;i+1<tmp.size();i++)
      |                  ~~~^~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2904 KB Correct: 2991 out of 500000 queries used.
2 Correct 2 ms 1884 KB Correct: 2994 out of 500000 queries used.
3 Correct 6 ms 8344 KB Correct: 4984 out of 500000 queries used.
4 Correct 5 ms 8464 KB Correct: 5079 out of 500000 queries used.
5 Correct 15 ms 8204 KB Correct: 5136 out of 500000 queries used.

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2904 KB Correct: 2991 out of 500000 queries used.
2 Correct 2 ms 1884 KB Correct: 2994 out of 500000 queries used.
3 Correct 6 ms 8344 KB Correct: 4984 out of 500000 queries used.
4 Correct 5 ms 8464 KB Correct: 5079 out of 500000 queries used.
5 Correct 15 ms 8204 KB Correct: 5136 out of 500000 queries used.
6 Correct 3 ms 6232 KB Correct: 2982 out of 500000 queries used.
7 Correct 15 ms 8464 KB Correct: 4370 out of 500000 queries used.
8 Correct 7 ms 8280 KB Correct: 5146 out of 500000 queries used.
9 Correct 8 ms 8540 KB Correct: 5718 out of 500000 queries used.
10 Correct 12 ms 8068 KB Correct: 5045 out of 500000 queries used.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5408 KB Correct: 2967 out of 12000 queries used.
2 Correct 2 ms 1884 KB Correct: 2973 out of 12000 queries used.
3 Correct 3 ms 3932 KB Correct: 2994 out of 12000 queries used.
4 Correct 2 ms 2392 KB Correct: 2973 out of 12000 queries used.
5 Correct 3 ms 4956 KB Correct: 2967 out of 12000 queries used.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5408 KB Correct: 2967 out of 12000 queries used.
2 Correct 2 ms 1884 KB Correct: 2973 out of 12000 queries used.
3 Correct 3 ms 3932 KB Correct: 2994 out of 12000 queries used.
4 Correct 2 ms 2392 KB Correct: 2973 out of 12000 queries used.
5 Correct 3 ms 4956 KB Correct: 2967 out of 12000 queries used.
6 Correct 2 ms 3164 KB Correct: 2988 out of 12000 queries used.
7 Correct 3 ms 4700 KB Correct: 2982 out of 12000 queries used.
8 Correct 4 ms 5724 KB Correct: 2994 out of 12000 queries used.
9 Correct 2 ms 3676 KB Correct: 2985 out of 12000 queries used.
10 Correct 2 ms 3676 KB Correct: 2976 out of 12000 queries used.

Subtask #5
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2904 KB Correct: 2991 out of 500000 queries used.
2 Correct 2 ms 1884 KB Correct: 2994 out of 500000 queries used.
3 Correct 6 ms 8344 KB Correct: 4984 out of 500000 queries used.
4 Correct 5 ms 8464 KB Correct: 5079 out of 500000 queries used.
5 Correct 15 ms 8204 KB Correct: 5136 out of 500000 queries used.
6 Correct 3 ms 6232 KB Correct: 2982 out of 500000 queries used.
7 Correct 15 ms 8464 KB Correct: 4370 out of 500000 queries used.
8 Correct 7 ms 8280 KB Correct: 5146 out of 500000 queries used.
9 Correct 8 ms 8540 KB Correct: 5718 out of 500000 queries used.
10 Correct 12 ms 8068 KB Correct: 5045 out of 500000 queries used.
11 Correct 3 ms 5408 KB Correct: 2967 out of 12000 queries used.
12 Correct 2 ms 1884 KB Correct: 2973 out of 12000 queries used.
13 Correct 3 ms 3932 KB Correct: 2994 out of 12000 queries used.
14 Correct 2 ms 2392 KB Correct: 2973 out of 12000 queries used.
15 Correct 3 ms 4956 KB Correct: 2967 out of 12000 queries used.
16 Correct 2 ms 3164 KB Correct: 2988 out of 12000 queries used.
17 Correct 3 ms 4700 KB Correct: 2982 out of 12000 queries used.
18 Correct 4 ms 5724 KB Correct: 2994 out of 12000 queries used.
19 Correct 2 ms 3676 KB Correct: 2985 out of 12000 queries used.
20 Correct 2 ms 3676 KB Correct: 2976 out of 12000 queries used.
21 Correct 2 ms 3160 KB Correct: 2982 out of 25000 queries used.
22 Correct 4 ms 7256 KB Correct: 3604 out of 25000 queries used.
23 Correct 3 ms 4184 KB Correct: 2993 out of 25000 queries used.
24 Correct 5 ms 7000 KB Correct: 3425 out of 25000 queries used.
25 Correct 6 ms 8280 KB Correct: 5167 out of 25000 queries used.
26 Correct 4 ms 8284 KB Correct: 4899 out of 25000 queries used.
27 Correct 5 ms 8468 KB Correct: 4992 out of 25000 queries used.
28 Correct 7 ms 8284 KB Correct: 5228 out of 25000 queries used.
29 Correct 7 ms 8524 KB Correct: 5344 out of 25000 queries used.
30 Correct 10 ms 8280 KB Correct: 5594 out of 25000 queries used.
31 Correct 7 ms 8792 KB Correct: 5498 out of 25000 queries used.
32 Correct 2 ms 1884 KB Correct: 2979 out of 25000 queries used.
33 Correct 7 ms 8284 KB Correct: 5441 out of 25000 queries used.
34 Correct 7 ms 8368 KB Correct: 5543 out of 25000 queries used.
35 Correct 7 ms 8280 KB Correct: 5475 out of 25000 queries used.
36 Correct 6 ms 8284 KB Correct: 5530 out of 25000 queries used.
37 Correct 6 ms 8464 KB Correct: 5537 out of 25000 queries used.
38 Correct 6 ms 8284 KB Correct: 5493 out of 25000 queries used.
39 Correct 6 ms 8284 KB Correct: 5486 out of 25000 queries used.
40 Correct 6 ms 8464 KB Correct: 5546 out of 25000 queries used.
41 Correct 7 ms 8540 KB Correct: 5478 out of 25000 queries used.
42 Correct 7 ms 8284 KB Correct: 5534 out of 25000 queries used.
43 Correct 3 ms 4188 KB Correct: 2988 out of 25000 queries used.
44 Correct 6 ms 8280 KB Correct: 5411 out of 25000 queries used.
45 Correct 7 ms 8284 KB Correct: 5476 out of 25000 queries used.
46 Correct 6 ms 8280 KB Correct: 5424 out of 25000 queries used.
47 Correct 6 ms 8540 KB Correct: 5560 out of 25000 queries used.
48 Correct 7 ms 8284 KB Correct: 5502 out of 25000 queries used.
49 Correct 6 ms 8544 KB Correct: 5526 out of 25000 queries used.
50 Correct 6 ms 8284 KB Correct: 5521 out of 25000 queries used.
51 Correct 7 ms 8520 KB Correct: 5502 out of 25000 queries used.
52 Correct 6 ms 8540 KB Correct: 5456 out of 25000 queries used.
53 Correct 8 ms 8340 KB Correct: 5668 out of 25000 queries used.
54 Correct 12 ms 8028 KB Correct: 4115 out of 25000 queries used.
55 Correct 9 ms 8284 KB Correct: 5469 out of 25000 queries used.
56 Correct 7 ms 8540 KB Correct: 5498 out of 25000 queries used.
57 Correct 10 ms 8380 KB Correct: 5694 out of 25000 queries used.
58 Correct 7 ms 8284 KB Correct: 5467 out of 25000 queries used.
59 Correct 7 ms 8464 KB Correct: 5469 out of 25000 queries used.
60 Correct 21 ms 8168 KB Correct: 5183 out of 25000 queries used.
61 Correct 14 ms 8024 KB Correct: 5091 out of 25000 queries used.
62 Correct 16 ms 7972 KB Correct: 5086 out of 25000 queries used.
63 Correct 11 ms 8024 KB Correct: 4795 out of 25000 queries used.
64 Correct 15 ms 7936 KB Correct: 5143 out of 25000 queries used.
65 Correct 8 ms 7256 KB Correct: 3857 out of 25000 queries used.
66 Correct 13 ms 8284 KB Correct: 5043 out of 25000 queries used.
67 Correct 3 ms 4700 KB Correct: 3040 out of 25000 queries used.
68 Correct 9 ms 7276 KB Correct: 3952 out of 25000 queries used.
69 Correct 12 ms 8284 KB Correct: 4176 out of 25000 queries used.
70 Correct 12 ms 8028 KB Correct: 4183 out of 25000 queries used.