oj.uz

Submission #1030206

# Submission time Handle Problem Language Result Execution time Memory
1030206 2024-07-21T23:03:10 Z boyliguanhan Swapping Cities (APIO20_swap) C++17
100 / 100
 438 ms 63284 KB 
#include "swap.h"

#include <bits/stdc++.h>
using namespace std;
vector<tuple<int,int,int>> edg;
int minyes[100100],abp[100100];
map<int,int> unpersist[100100];
vector<int>v[100100];
vector<pair<int,int>> roots;
int derot,N_;
void upd(int t,int p,int v){
    unpersist[p][t]=v;
}
void do_a_merge(int &x,int &y,int t){
    if(v[x].size()<v[y].size())
        swap(x,y);
    for(auto k:v[y])
        upd(t,k,x),abp[k]=x,v[x].push_back(k);
    v[y].clear();
}
int par[100100],deg[100100];
bitset<100100>yes;
void init(int N,int M,vector<int>U,vector<int>V,vector<int>W) {
    for(int i=1;i<=N;i++)
        unpersist[i][-1]=i,abp[i]=i;
    N_=N;
    for(int i=1;i<=N;i++)
        v[i].push_back(i);
    for(int i=0;i<M;i++)
        edg.push_back({W[i],++U[i],++V[i]});
    for(auto&i:minyes)i=1e9+1;
    sort(edg.begin(),edg.end());
    int prevW=get<0>(edg[0]);
    for(auto[w,u,v]:edg){
        deg[u]++,deg[v]++;
        if(deg[u]>2&&!yes[abp[u]])
            yes[abp[u]]=1,minyes[abp[u]]=w;
        if(deg[v]>2&&!yes[abp[v]])
            yes[abp[v]]=1,minyes[abp[v]]=w;
        u=abp[u],v=abp[v];
        if(u-v) {
            do_a_merge(u,v,w);
            if(!yes[u]&&yes[v])
                yes[u]=1,minyes[u]=w;
        } else if(!yes[v])
            yes[v]=1,minyes[v]=w;
        prevW=w;
    }
}
int ok(int t,int x,int y){
    x=(--unpersist[x].upper_bound(t))->second;
    y=(--unpersist[y].upper_bound(t))->second;
    return x==y&&minyes[x]<=t;
}
int getMinimumFuelCapacity(int X,int Y) {
    ++X,++Y;
    int l=1,r=1e9,res=-1;
    while(l<=r){
        int mid=l+r>>1;
        if(ok(mid,X,Y)){
            r=mid-1,res=mid;
        } else {
            l=mid+1;
        }
    }
    return res;
}

Compilation message

swap.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
swap.cpp:33:9: warning: variable 'prevW' set but not used [-Wunused-but-set-variable]
   33 |     int prevW=get<0>(edg[0]);
      |         ^~~~~
swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:59:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   59 |         int mid=l+r>>1;
      |                 ~^~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7772 KB Output is correct
2 Correct 3 ms 7772 KB Output is correct
3 Correct 3 ms 7772 KB Output is correct
4 Correct 3 ms 8028 KB Output is correct
5 Correct 4 ms 8024 KB Output is correct
6 Correct 4 ms 8028 KB Output is correct
7 Correct 4 ms 8028 KB Output is correct
8 Correct 4 ms 8048 KB Output is correct
9 Correct 122 ms 43092 KB Output is correct
10 Correct 180 ms 50312 KB Output is correct
11 Correct 153 ms 49312 KB Output is correct
12 Correct 178 ms 52172 KB Output is correct
13 Correct 73 ms 29716 KB Output is correct
14 Correct 133 ms 42948 KB Output is correct
15 Correct 405 ms 55520 KB Output is correct
16 Correct 388 ms 53880 KB Output is correct
17 Correct 397 ms 57020 KB Output is correct
18 Correct 181 ms 33844 KB Output is correct
19 Correct 127 ms 18960 KB Output is correct
20 Correct 418 ms 56556 KB Output is correct
21 Correct 382 ms 55128 KB Output is correct
22 Correct 438 ms 58164 KB Output is correct
23 Correct 179 ms 35124 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7772 KB Output is correct
2 Correct 3 ms 7772 KB Output is correct
3 Correct 206 ms 31032 KB Output is correct
4 Correct 184 ms 31532 KB Output is correct
5 Correct 182 ms 31584 KB Output is correct
6 Correct 213 ms 31532 KB Output is correct
7 Correct 209 ms 31596 KB Output is correct
8 Correct 190 ms 30756 KB Output is correct
9 Correct 192 ms 31300 KB Output is correct
10 Correct 193 ms 30808 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7772 KB Output is correct
2 Correct 3 ms 7772 KB Output is correct
3 Correct 3 ms 7772 KB Output is correct
4 Correct 3 ms 8028 KB Output is correct
5 Correct 4 ms 8024 KB Output is correct
6 Correct 4 ms 8028 KB Output is correct
7 Correct 4 ms 8028 KB Output is correct
8 Correct 4 ms 8048 KB Output is correct
9 Correct 3 ms 7772 KB Output is correct
10 Correct 4 ms 8028 KB Output is correct
11 Correct 4 ms 8028 KB Output is correct
12 Correct 4 ms 8028 KB Output is correct
13 Correct 4 ms 8024 KB Output is correct
14 Correct 4 ms 8028 KB Output is correct
15 Correct 4 ms 8028 KB Output is correct
16 Correct 4 ms 8028 KB Output is correct
17 Correct 3 ms 8028 KB Output is correct
18 Correct 4 ms 8028 KB Output is correct
19 Correct 3 ms 8028 KB Output is correct
20 Correct 4 ms 8024 KB Output is correct
21 Correct 3 ms 8028 KB Output is correct
22 Correct 4 ms 8028 KB Output is correct
23 Correct 4 ms 8028 KB Output is correct
24 Correct 4 ms 8028 KB Output is correct
25 Correct 4 ms 8028 KB Output is correct
26 Correct 4 ms 8284 KB Output is correct
27 Correct 3 ms 8028 KB Output is correct
28 Correct 4 ms 8028 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7772 KB Output is correct
2 Correct 4 ms 7772 KB Output is correct
3 Correct 3 ms 7772 KB Output is correct
4 Correct 3 ms 7772 KB Output is correct
5 Correct 3 ms 8028 KB Output is correct
6 Correct 4 ms 8024 KB Output is correct
7 Correct 4 ms 8028 KB Output is correct
8 Correct 4 ms 8028 KB Output is correct
9 Correct 4 ms 8048 KB Output is correct
10 Correct 122 ms 43092 KB Output is correct
11 Correct 180 ms 50312 KB Output is correct
12 Correct 153 ms 49312 KB Output is correct
13 Correct 178 ms 52172 KB Output is correct
14 Correct 73 ms 29716 KB Output is correct
15 Correct 4 ms 8028 KB Output is correct
16 Correct 4 ms 8028 KB Output is correct
17 Correct 4 ms 8028 KB Output is correct
18 Correct 4 ms 8024 KB Output is correct
19 Correct 4 ms 8028 KB Output is correct
20 Correct 4 ms 8028 KB Output is correct
21 Correct 4 ms 8028 KB Output is correct
22 Correct 3 ms 8028 KB Output is correct
23 Correct 4 ms 8028 KB Output is correct
24 Correct 3 ms 8028 KB Output is correct
25 Correct 4 ms 8024 KB Output is correct
26 Correct 3 ms 8028 KB Output is correct
27 Correct 4 ms 8028 KB Output is correct
28 Correct 4 ms 8028 KB Output is correct
29 Correct 4 ms 8028 KB Output is correct
30 Correct 4 ms 8028 KB Output is correct
31 Correct 4 ms 8284 KB Output is correct
32 Correct 3 ms 8028 KB Output is correct
33 Correct 4 ms 8028 KB Output is correct
34 Correct 17 ms 12320 KB Output is correct
35 Correct 187 ms 51652 KB Output is correct
36 Correct 167 ms 50376 KB Output is correct
37 Correct 146 ms 48836 KB Output is correct
38 Correct 139 ms 46028 KB Output is correct
39 Correct 133 ms 45044 KB Output is correct
40 Correct 108 ms 40388 KB Output is correct
41 Correct 174 ms 53092 KB Output is correct
42 Correct 163 ms 52936 KB Output is correct
43 Correct 64 ms 28620 KB Output is correct
44 Correct 124 ms 43976 KB Output is correct
45 Correct 88 ms 31340 KB Output is correct
46 Correct 158 ms 50628 KB Output is correct
47 Correct 117 ms 39876 KB Output is correct
48 Correct 89 ms 32452 KB Output is correct
49 Correct 42 ms 17096 KB Output is correct
50 Correct 35 ms 15828 KB Output is correct
51 Correct 76 ms 27316 KB Output is correct
52 Correct 168 ms 51276 KB Output is correct
53 Correct 126 ms 40148 KB Output is correct
54 Correct 192 ms 58072 KB Output is correct
55 Correct 69 ms 28872 KB Output is correct
56 Correct 106 ms 37180 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7772 KB Output is correct
2 Correct 3 ms 7772 KB Output is correct
3 Correct 3 ms 7772 KB Output is correct
4 Correct 3 ms 8028 KB Output is correct
5 Correct 4 ms 8024 KB Output is correct
6 Correct 4 ms 8028 KB Output is correct
7 Correct 4 ms 8028 KB Output is correct
8 Correct 4 ms 8048 KB Output is correct
9 Correct 122 ms 43092 KB Output is correct
10 Correct 180 ms 50312 KB Output is correct
11 Correct 153 ms 49312 KB Output is correct
12 Correct 178 ms 52172 KB Output is correct
13 Correct 73 ms 29716 KB Output is correct
14 Correct 133 ms 42948 KB Output is correct
15 Correct 405 ms 55520 KB Output is correct
16 Correct 388 ms 53880 KB Output is correct
17 Correct 397 ms 57020 KB Output is correct
18 Correct 181 ms 33844 KB Output is correct
19 Correct 206 ms 31032 KB Output is correct
20 Correct 184 ms 31532 KB Output is correct
21 Correct 182 ms 31584 KB Output is correct
22 Correct 213 ms 31532 KB Output is correct
23 Correct 209 ms 31596 KB Output is correct
24 Correct 190 ms 30756 KB Output is correct
25 Correct 192 ms 31300 KB Output is correct
26 Correct 193 ms 30808 KB Output is correct
27 Correct 4 ms 8028 KB Output is correct
28 Correct 4 ms 8028 KB Output is correct
29 Correct 4 ms 8028 KB Output is correct
30 Correct 4 ms 8024 KB Output is correct
31 Correct 4 ms 8028 KB Output is correct
32 Correct 4 ms 8028 KB Output is correct
33 Correct 4 ms 8028 KB Output is correct
34 Correct 3 ms 8028 KB Output is correct
35 Correct 4 ms 8028 KB Output is correct
36 Correct 17 ms 12320 KB Output is correct
37 Correct 187 ms 51652 KB Output is correct
38 Correct 167 ms 50376 KB Output is correct
39 Correct 146 ms 48836 KB Output is correct
40 Correct 139 ms 46028 KB Output is correct
41 Correct 133 ms 45044 KB Output is correct
42 Correct 108 ms 40388 KB Output is correct
43 Correct 174 ms 53092 KB Output is correct
44 Correct 163 ms 52936 KB Output is correct
45 Correct 64 ms 28620 KB Output is correct
46 Correct 124 ms 43976 KB Output is correct
47 Correct 31 ms 12564 KB Output is correct
48 Correct 370 ms 56664 KB Output is correct
49 Correct 334 ms 54580 KB Output is correct
50 Correct 331 ms 54288 KB Output is correct
51 Correct 297 ms 52276 KB Output is correct
52 Correct 291 ms 47824 KB Output is correct
53 Correct 223 ms 37052 KB Output is correct
54 Correct 325 ms 57148 KB Output is correct
55 Correct 399 ms 58292 KB Output is correct
56 Correct 191 ms 34096 KB Output is correct
57 Correct 313 ms 48412 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7772 KB Output is correct
2 Correct 4 ms 7772 KB Output is correct
3 Correct 3 ms 7772 KB Output is correct
4 Correct 3 ms 7772 KB Output is correct
5 Correct 3 ms 8028 KB Output is correct
6 Correct 4 ms 8024 KB Output is correct
7 Correct 4 ms 8028 KB Output is correct
8 Correct 4 ms 8028 KB Output is correct
9 Correct 4 ms 8048 KB Output is correct
10 Correct 122 ms 43092 KB Output is correct
11 Correct 180 ms 50312 KB Output is correct
12 Correct 153 ms 49312 KB Output is correct
13 Correct 178 ms 52172 KB Output is correct
14 Correct 73 ms 29716 KB Output is correct
15 Correct 133 ms 42948 KB Output is correct
16 Correct 405 ms 55520 KB Output is correct
17 Correct 388 ms 53880 KB Output is correct
18 Correct 397 ms 57020 KB Output is correct
19 Correct 181 ms 33844 KB Output is correct
20 Correct 206 ms 31032 KB Output is correct
21 Correct 184 ms 31532 KB Output is correct
22 Correct 182 ms 31584 KB Output is correct
23 Correct 213 ms 31532 KB Output is correct
24 Correct 209 ms 31596 KB Output is correct
25 Correct 190 ms 30756 KB Output is correct
26 Correct 192 ms 31300 KB Output is correct
27 Correct 193 ms 30808 KB Output is correct
28 Correct 4 ms 8028 KB Output is correct
29 Correct 4 ms 8028 KB Output is correct
30 Correct 4 ms 8028 KB Output is correct
31 Correct 4 ms 8024 KB Output is correct
32 Correct 4 ms 8028 KB Output is correct
33 Correct 4 ms 8028 KB Output is correct
34 Correct 4 ms 8028 KB Output is correct
35 Correct 3 ms 8028 KB Output is correct
36 Correct 4 ms 8028 KB Output is correct
37 Correct 17 ms 12320 KB Output is correct
38 Correct 187 ms 51652 KB Output is correct
39 Correct 167 ms 50376 KB Output is correct
40 Correct 146 ms 48836 KB Output is correct
41 Correct 139 ms 46028 KB Output is correct
42 Correct 133 ms 45044 KB Output is correct
43 Correct 108 ms 40388 KB Output is correct
44 Correct 174 ms 53092 KB Output is correct
45 Correct 163 ms 52936 KB Output is correct
46 Correct 64 ms 28620 KB Output is correct
47 Correct 124 ms 43976 KB Output is correct
48 Correct 31 ms 12564 KB Output is correct
49 Correct 370 ms 56664 KB Output is correct
50 Correct 334 ms 54580 KB Output is correct
51 Correct 331 ms 54288 KB Output is correct
52 Correct 297 ms 52276 KB Output is correct
53 Correct 291 ms 47824 KB Output is correct
54 Correct 223 ms 37052 KB Output is correct
55 Correct 325 ms 57148 KB Output is correct
56 Correct 399 ms 58292 KB Output is correct
57 Correct 191 ms 34096 KB Output is correct
58 Correct 313 ms 48412 KB Output is correct
59 Correct 127 ms 18960 KB Output is correct
60 Correct 418 ms 56556 KB Output is correct
61 Correct 382 ms 55128 KB Output is correct
62 Correct 438 ms 58164 KB Output is correct
63 Correct 179 ms 35124 KB Output is correct
64 Correct 3 ms 8028 KB Output is correct
65 Correct 4 ms 8024 KB Output is correct
66 Correct 3 ms 8028 KB Output is correct
67 Correct 4 ms 8028 KB Output is correct
68 Correct 4 ms 8028 KB Output is correct
69 Correct 4 ms 8028 KB Output is correct
70 Correct 4 ms 8028 KB Output is correct
71 Correct 4 ms 8284 KB Output is correct
72 Correct 3 ms 8028 KB Output is correct
73 Correct 4 ms 8028 KB Output is correct
74 Correct 88 ms 31340 KB Output is correct
75 Correct 158 ms 50628 KB Output is correct
76 Correct 117 ms 39876 KB Output is correct
77 Correct 89 ms 32452 KB Output is correct
78 Correct 42 ms 17096 KB Output is correct
79 Correct 35 ms 15828 KB Output is correct
80 Correct 76 ms 27316 KB Output is correct
81 Correct 168 ms 51276 KB Output is correct
82 Correct 126 ms 40148 KB Output is correct
83 Correct 192 ms 58072 KB Output is correct
84 Correct 69 ms 28872 KB Output is correct
85 Correct 106 ms 37180 KB Output is correct
86 Correct 61 ms 17604 KB Output is correct
87 Correct 352 ms 52816 KB Output is correct
88 Correct 305 ms 53548 KB Output is correct
89 Correct 210 ms 36192 KB Output is correct
90 Correct 176 ms 20980 KB Output is correct
91 Correct 164 ms 22468 KB Output is correct
92 Correct 202 ms 32300 KB Output is correct
93 Correct 306 ms 53704 KB Output is correct
94 Correct 282 ms 45872 KB Output is correct
95 Correct 396 ms 63284 KB Output is correct
96 Correct 172 ms 34128 KB Output is correct
97 Correct 237 ms 40844 KB Output is correct