oj.uz

Submission #93621

# Submission time Handle Problem Language Result Execution time Memory
93621 2019-01-10T11:20:58 Z admin City Mapping (NOI18_citymapping) C++17
95.7 / 100
 29 ms 12412 KB 
#include "citymapping.h"
#include<bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
const ll LINF = 0x3f3f3f3f3f3f3f3f;
 
vector<pll> lis;
ll di[1010][1010];
vector<pll> ttis[1010];
int par[1010];
int perm[1010], invperm[1010];
 
ll calc(int u, int v) {
    if (di[u][v]) return di[u][v];
    if (u==v) return 0;
    ll d = get_distance(perm[u], perm[v]);
    di[u][v] = di[v][u] = d;
    return d;
}
 
int head, q;
int dir[1010][1010];
void add(int u, int v, int A[], int B[], int W[]) {
    A[q] = u;
    B[q] = v;
    W[q] = calc(head,v)-calc(head,u);
    par[v] = u;
    ttis[u].push_back(pll(W[q],v));
    int p = v;
    while(p!=head) {
        int pp = par[p];
        for (int i=0;i<ttis[pp].size();i++) if (ttis[pp][i].second==p) {
            dir[pp][v] = i;
            break;
        }
        p = pp;
    }
    q++;
}
 
int D[1010], E[1010];
void dfs(int here) {
    for (pll &tmp : ttis[here]) {
        dfs(tmp.second);
    }
    if (ttis[here].empty()) {
        D[here] = 0;
        E[here] = here;
        return;
    }
    if (ttis[here].size()==1) {
        D[here]=D[ttis[here][0].second];
        E[here]=E[ttis[here][0].second];
        return;
    }
    int t = (D[ttis[here][0].second]>D[ttis[here][1].second]?0:1);
    D[here]=max(D[ttis[here][t].second]-1,D[ttis[here][1-t].second])+1;
    E[here]=E[ttis[here][t].second];
}
 
void find_roads(int n, int Q, int A[], int B[], int W[]) {
  for(int i=0;i<n;i++)perm[i]=i+1;
  random_shuffle(perm, perm+n);
  for(int i=0;i<n;i++)invperm[perm[i]]=i;
  
    memset(par,-1,sizeof(par));
    int i, j;
    ll maxi = 0;
    for (i=1;i<n;i++) {
        if (maxi<calc(0,i)) {
            maxi=calc(0,i);
            head=i;
        }
    }
    //printf("\n%d\n",head);
    vector<pll> pis;
    for (i=0;i<n;i++) {
        //if (calc(head,i)+calc(0,i)==calc(0,head)) {
        //    pis.push_back(pll(calc(i,head),i));
        //}
        //else
        lis.push_back(pll(calc(i,head),i));
    }
    //sort(pis.begin(),pis.end());
    //for (j=1;j<pis.size();j++) {
    //    add(pis[j-1].second,pis[j].second);
    //}
    sort(lis.begin(),lis.end());
    add(lis[0].second,lis[1].second,A,B,W);
    for (j=2;j<lis.size();j++) {
        dfs(lis[1].second);
        int idx = lis[j].second;
        ll mini = LINF;
        int p = lis[1].second;
        while(!ttis[p].empty()) {
            ll d = (calc(head,idx)+calc(head,E[p])-calc(E[p],idx))/2;
            int v = E[p];
            while(calc(head,p)<d) {
                p = ttis[p][dir[p][v]].second;
            }
            if (ttis[p].size()<=1) break;
            p = ttis[p][1-dir[p][v]].second;
        }
        add(p,idx,A,B,W);
    }
  for(int i =0 ;i<n-1;i++)A[i]=perm[A[i]],B[i]=perm[B[i]];
}

Compilation message

citymapping.cpp: In function 'void add(int, int, int*, int*, int*)':
citymapping.cpp:37:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i=0;i<ttis[pp].size();i++) if (ttis[pp][i].second==p) {
                      ~^~~~~~~~~~~~~~~~
citymapping.cpp: In function 'void find_roads(int, int, int*, int*, int*)':
citymapping.cpp:95:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (j=2;j<lis.size();j++) {
              ~^~~~~~~~~~~
citymapping.cpp:98:12: warning: unused variable 'mini' [-Wunused-variable]
         ll mini = LINF;
            ^~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 11772 KB Correct: 2989 out of 500000 queries used.
2 Correct 20 ms 11256 KB Correct: 3251 out of 500000 queries used.
3 Correct 15 ms 11256 KB Correct: 5353 out of 500000 queries used.
4 Correct 13 ms 10872 KB Correct: 6369 out of 500000 queries used.
5 Correct 17 ms 11868 KB Correct: 3851 out of 500000 queries used.

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 11772 KB Correct: 2989 out of 500000 queries used.
2 Correct 20 ms 11256 KB Correct: 3251 out of 500000 queries used.
3 Correct 15 ms 11256 KB Correct: 5353 out of 500000 queries used.
4 Correct 13 ms 10872 KB Correct: 6369 out of 500000 queries used.
5 Correct 17 ms 11868 KB Correct: 3851 out of 500000 queries used.
6 Correct 26 ms 11768 KB Correct: 2980 out of 500000 queries used.
7 Correct 20 ms 10196 KB Correct: 2986 out of 500000 queries used.
8 Correct 15 ms 11132 KB Correct: 5374 out of 500000 queries used.
9 Correct 15 ms 11000 KB Correct: 6138 out of 500000 queries used.
10 Correct 18 ms 12280 KB Correct: 3905 out of 500000 queries used.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 12024 KB Correct: 2965 out of 12000 queries used.
2 Correct 27 ms 12284 KB Correct: 2971 out of 12000 queries used.
3 Correct 28 ms 11944 KB Correct: 2992 out of 12000 queries used.
4 Correct 26 ms 12412 KB Correct: 2971 out of 12000 queries used.
5 Correct 26 ms 11512 KB Correct: 2965 out of 12000 queries used.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 12024 KB Correct: 2965 out of 12000 queries used.
2 Correct 27 ms 12284 KB Correct: 2971 out of 12000 queries used.
3 Correct 28 ms 11944 KB Correct: 2992 out of 12000 queries used.
4 Correct 26 ms 12412 KB Correct: 2971 out of 12000 queries used.
5 Correct 26 ms 11512 KB Correct: 2965 out of 12000 queries used.
6 Correct 26 ms 12408 KB Correct: 2986 out of 12000 queries used.
7 Correct 28 ms 12336 KB Correct: 2980 out of 12000 queries used.
8 Correct 27 ms 12280 KB Correct: 2992 out of 12000 queries used.
9 Correct 27 ms 11768 KB Correct: 2983 out of 12000 queries used.
10 Correct 29 ms 12152 KB Correct: 2974 out of 12000 queries used.

Subtask #5
38.7 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 11772 KB Correct: 2989 out of 500000 queries used.
2 Correct 20 ms 11256 KB Correct: 3251 out of 500000 queries used.
3 Correct 15 ms 11256 KB Correct: 5353 out of 500000 queries used.
4 Correct 13 ms 10872 KB Correct: 6369 out of 500000 queries used.
5 Correct 17 ms 11868 KB Correct: 3851 out of 500000 queries used.
6 Correct 26 ms 11768 KB Correct: 2980 out of 500000 queries used.
7 Correct 20 ms 10196 KB Correct: 2986 out of 500000 queries used.
8 Correct 15 ms 11132 KB Correct: 5374 out of 500000 queries used.
9 Correct 15 ms 11000 KB Correct: 6138 out of 500000 queries used.
10 Correct 18 ms 12280 KB Correct: 3905 out of 500000 queries used.
11 Correct 29 ms 12024 KB Correct: 2965 out of 12000 queries used.
12 Correct 27 ms 12284 KB Correct: 2971 out of 12000 queries used.
13 Correct 28 ms 11944 KB Correct: 2992 out of 12000 queries used.
14 Correct 26 ms 12412 KB Correct: 2971 out of 12000 queries used.
15 Correct 26 ms 11512 KB Correct: 2965 out of 12000 queries used.
16 Correct 26 ms 12408 KB Correct: 2986 out of 12000 queries used.
17 Correct 28 ms 12336 KB Correct: 2980 out of 12000 queries used.
18 Correct 27 ms 12280 KB Correct: 2992 out of 12000 queries used.
19 Correct 27 ms 11768 KB Correct: 2983 out of 12000 queries used.
20 Correct 29 ms 12152 KB Correct: 2974 out of 12000 queries used.
21 Correct 25 ms 11896 KB Correct: 2980 out of 25000 queries used.
22 Correct 20 ms 11252 KB Correct: 3506 out of 25000 queries used.
23 Correct 20 ms 10360 KB Correct: 3509 out of 25000 queries used.
24 Correct 20 ms 10872 KB Correct: 3491 out of 25000 queries used.
25 Correct 15 ms 11256 KB Correct: 5283 out of 25000 queries used.
26 Correct 17 ms 11188 KB Correct: 5255 out of 25000 queries used.
27 Correct 17 ms 11256 KB Correct: 5141 out of 25000 queries used.
28 Correct 16 ms 11128 KB Correct: 5386 out of 25000 queries used.
29 Correct 17 ms 11256 KB Correct: 5449 out of 25000 queries used.
30 Correct 16 ms 11128 KB Correct: 5396 out of 25000 queries used.
31 Correct 16 ms 11004 KB Correct: 6190 out of 25000 queries used.
32 Correct 28 ms 12408 KB Correct: 2977 out of 25000 queries used.
33 Correct 15 ms 10872 KB Correct: 6491 out of 25000 queries used.
34 Correct 14 ms 10872 KB Correct: 6519 out of 25000 queries used.
35 Correct 15 ms 10872 KB Correct: 6330 out of 25000 queries used.
36 Correct 16 ms 11000 KB Correct: 6365 out of 25000 queries used.
37 Correct 16 ms 10872 KB Correct: 6400 out of 25000 queries used.
38 Correct 16 ms 11000 KB Correct: 6322 out of 25000 queries used.
39 Correct 16 ms 10972 KB Correct: 6278 out of 25000 queries used.
40 Correct 16 ms 11000 KB Correct: 6520 out of 25000 queries used.
41 Correct 16 ms 11000 KB Correct: 6166 out of 25000 queries used.
42 Correct 16 ms 11000 KB Correct: 6249 out of 25000 queries used.
43 Correct 28 ms 12024 KB Correct: 2986 out of 25000 queries used.
44 Correct 16 ms 10872 KB Correct: 6343 out of 25000 queries used.
45 Correct 16 ms 10872 KB Correct: 6230 out of 25000 queries used.
46 Correct 16 ms 10872 KB Correct: 6364 out of 25000 queries used.
47 Correct 14 ms 10872 KB Correct: 6335 out of 25000 queries used.
48 Correct 15 ms 10972 KB Correct: 6738 out of 25000 queries used.
49 Correct 16 ms 10872 KB Correct: 6492 out of 25000 queries used.
50 Correct 15 ms 11000 KB Correct: 6310 out of 25000 queries used.
51 Correct 18 ms 10872 KB Correct: 6252 out of 25000 queries used.
52 Correct 17 ms 11000 KB Correct: 6268 out of 25000 queries used.
53 Correct 16 ms 11000 KB Correct: 6400 out of 25000 queries used.
54 Correct 21 ms 11512 KB Correct: 3493 out of 25000 queries used.
55 Correct 16 ms 10872 KB Correct: 6224 out of 25000 queries used.
56 Correct 14 ms 11000 KB Correct: 5925 out of 25000 queries used.
57 Correct 14 ms 11000 KB Correct: 6229 out of 25000 queries used.
58 Correct 14 ms 10744 KB Correct: 5890 out of 25000 queries used.
59 Correct 15 ms 10976 KB Correct: 6653 out of 25000 queries used.
60 Correct 18 ms 12152 KB Correct: 3825 out of 25000 queries used.
61 Correct 18 ms 12280 KB Correct: 4520 out of 25000 queries used.
62 Correct 19 ms 12280 KB Correct: 3820 out of 25000 queries used.
63 Correct 18 ms 12152 KB Correct: 3848 out of 25000 queries used.
64 Correct 18 ms 12280 KB Correct: 3877 out of 25000 queries used.
65 Correct 19 ms 9848 KB Correct: 3461 out of 25000 queries used.
66 Correct 19 ms 12408 KB Correct: 4647 out of 25000 queries used.
67 Correct 20 ms 10616 KB Correct: 3507 out of 25000 queries used.
68 Correct 21 ms 11004 KB Correct: 3463 out of 25000 queries used.
69 Correct 20 ms 10964 KB Correct: 3011 out of 25000 queries used.
70 Correct 19 ms 9464 KB Correct: 3470 out of 25000 queries used.