oj.uz

Submission #313590

# Submission time Handle Problem Language Result Execution time Memory
313590 2020-10-16T10:38:30 Z juggernaut Swapping Cities (APIO20_swap) C++14
100 / 100
 746 ms 52840 KB 
//#include"grader.cpp"
#include"swap.h"
#include<bits/stdc++.h>
#define fr first
#define sc second
using namespace std;
vector<pair<int,int>>g[100005];
vector<int>child[100005];
int timer,tin[100005],tout[100005],up[100005][17],sp1[100005][17],sp2[100005][17],inf=2e9,par[100005],deg[100005];
int fin(int v){
    if(v==par[v])return v;
    return par[v]=fin(par[v]);
}
void dfs(int v,int p,int cost){
    tin[v]=++timer;
    up[v][0]=p;
    sp1[v][0]=cost;
    for(int i=1;i<17;i++){
        up[v][i]=up[up[v][i-1]][i-1];
        sp1[v][i]=max(sp1[v][i-1],sp1[up[v][i-1]][i-1]);
        sp2[v][i]=min(sp2[v][i-1],sp2[up[v][i-1]][i-1]);
    }
    for(auto to:g[v])if(to.fr!=p)dfs(to.fr,v,to.sc);
    tout[v]=++timer;
}
bool upper(int a,int b){
    return tin[a]<tin[b]&&tout[a]>tout[b];
}
int lca(int a,int b){
	if(upper(a,b))return a;
	if(upper(b,a))return b;
	for(int i=16;i>=0;i--)if(!upper(up[a][i],b))a=up[a][i];
	return up[a][0];
}
int fin1(int a,int p){
    int res=0;
    for(int i=16;i>=0;i--)
        if(!upper(up[a][i],p)){
            res=max(res,sp1[a][i]);
            a=up[a][i];
        }
    return res;
}
int fin2(int a,int p){
    int res=inf;
    for(int i=16;i>=0;i--)
        if(!upper(up[a][i],p)){
            res=min(res,sp2[a][i]);
            a=up[a][i];
        }
    return res;
}
bool cmp(pair<int,int>l,pair<int,int>r){
    return l.sc<r.sc;
}
void add_edge(int a,int b,int c){
    int aa=fin(a),bb=fin(b);
    deg[a]++;
    deg[b]++;
    if(aa!=bb){
        if( sp2[aa][0]==inf && ( sp2[bb][0]!=inf ||deg[a]==3||deg[b]==3 )){
            for(int i = 0; i<child[aa].size(); i++){
                sp2[child[aa][i]][0]=c;
            }
            child[aa].clear();
        }
        if( sp2[bb][0]==inf && ( sp2[aa][0]!=inf ||deg[a]==3||deg[b]==3 )){
            for(int i = 0; i<child[bb].size(); i++){
                sp2[child[bb][i]][0]=c;
            }
            child[bb].clear();
        }
        g[a].push_back({b,c});
        g[b].push_back({a,c});
        if(child[aa].size()<child[bb].size())swap(aa,bb);
        par[bb]=aa;
        child[aa].insert(child[aa].end(),child[bb].begin(),child[bb].end());
        child[bb].clear();
    }else{
        if(sp2[aa][0]==inf){
            for(int i = 0; i<child[aa].size(); i++){
                sp2[child[aa][i]][0]=c;
            }
            child[aa].clear();
        }
    }
}
bool cmp2(pair<pair<int,int>,int>l,pair<pair<int,int>,int>r){
    return l.sc<r.sc;
}
void init(int N,int M,vector<int>U,vector<int>V,vector<int>W){
    for(int i=0;i<N;i++)child[i].push_back(i),par[i]=i,sp2[i][0]=inf;
    vector<pair<pair<int,int>,int>>ed;
    for(int i=0;i<M;i++)ed.push_back({{U[i],V[i]},W[i]});
    sort(ed.begin(),ed.end(),cmp2);
    for(auto to:ed)
        add_edge(to.fr.fr,to.fr.sc,to.sc);
    for(int i=0;i<N;i++)sort(g[i].begin(),g[i].end(),cmp);
    dfs(0,0,0);
}
int getMinimumFuelCapacity(int X,int Y){
    int l=lca(X,Y),res;
    res=max(min(fin2(X,l),fin2(Y,l)),max(fin1(X,l),fin1(Y,l)));
    if(res==inf)res=-1;
    return res;
}

Compilation message

swap.cpp: In function 'void add_edge(int, int, int)':
swap.cpp:62:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |             for(int i = 0; i<child[aa].size(); i++){
      |                            ~^~~~~~~~~~~~~~~~~
swap.cpp:68:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |             for(int i = 0; i<child[bb].size(); i++){
      |                            ~^~~~~~~~~~~~~~~~~
swap.cpp:81:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |             for(int i = 0; i<child[aa].size(); i++){
      |                            ~^~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4992 KB Output is correct
2 Correct 4 ms 5120 KB Output is correct
3 Correct 4 ms 4992 KB Output is correct
4 Correct 4 ms 5248 KB Output is correct
5 Correct 5 ms 5376 KB Output is correct
6 Correct 5 ms 5376 KB Output is correct
7 Correct 5 ms 5408 KB Output is correct
8 Correct 5 ms 5504 KB Output is correct
9 Correct 204 ms 36460 KB Output is correct
10 Correct 257 ms 43756 KB Output is correct
11 Correct 248 ms 43240 KB Output is correct
12 Correct 263 ms 45676 KB Output is correct
13 Correct 222 ms 43852 KB Output is correct
14 Correct 236 ms 36204 KB Output is correct
15 Correct 627 ms 48140 KB Output is correct
16 Correct 599 ms 45932 KB Output is correct
17 Correct 667 ms 50412 KB Output is correct
18 Correct 607 ms 47340 KB Output is correct
19 Correct 178 ms 16508 KB Output is correct
20 Correct 602 ms 47724 KB Output is correct
21 Correct 611 ms 46552 KB Output is correct
22 Correct 653 ms 49332 KB Output is correct
23 Correct 606 ms 47032 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4992 KB Output is correct
2 Correct 4 ms 5120 KB Output is correct
3 Correct 382 ms 41140 KB Output is correct
4 Correct 395 ms 42552 KB Output is correct
5 Correct 399 ms 42012 KB Output is correct
6 Correct 380 ms 42432 KB Output is correct
7 Correct 437 ms 42496 KB Output is correct
8 Correct 380 ms 40908 KB Output is correct
9 Correct 408 ms 41968 KB Output is correct
10 Correct 381 ms 40692 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4992 KB Output is correct
2 Correct 4 ms 4992 KB Output is correct
3 Correct 4 ms 5120 KB Output is correct
4 Correct 4 ms 4992 KB Output is correct
5 Correct 4 ms 5248 KB Output is correct
6 Correct 5 ms 5376 KB Output is correct
7 Correct 5 ms 5376 KB Output is correct
8 Correct 5 ms 5408 KB Output is correct
9 Correct 5 ms 5504 KB Output is correct
10 Correct 5 ms 5376 KB Output is correct
11 Correct 5 ms 5376 KB Output is correct
12 Correct 5 ms 5376 KB Output is correct
13 Correct 4 ms 5280 KB Output is correct
14 Correct 5 ms 5376 KB Output is correct
15 Correct 5 ms 5376 KB Output is correct
16 Correct 6 ms 5376 KB Output is correct
17 Correct 5 ms 5504 KB Output is correct
18 Correct 5 ms 5376 KB Output is correct
19 Correct 5 ms 5376 KB Output is correct
20 Correct 5 ms 5376 KB Output is correct
21 Correct 5 ms 5376 KB Output is correct
22 Correct 5 ms 5248 KB Output is correct
23 Correct 5 ms 5248 KB Output is correct
24 Correct 6 ms 5504 KB Output is correct
25 Correct 5 ms 5376 KB Output is correct
26 Correct 5 ms 5504 KB Output is correct
27 Correct 5 ms 5376 KB Output is correct
28 Correct 6 ms 5376 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4992 KB Output is correct
2 Correct 4 ms 4992 KB Output is correct
3 Correct 4 ms 5120 KB Output is correct
4 Correct 4 ms 4992 KB Output is correct
5 Correct 4 ms 5248 KB Output is correct
6 Correct 5 ms 5376 KB Output is correct
7 Correct 5 ms 5376 KB Output is correct
8 Correct 5 ms 5408 KB Output is correct
9 Correct 5 ms 5504 KB Output is correct
10 Correct 204 ms 36460 KB Output is correct
11 Correct 257 ms 43756 KB Output is correct
12 Correct 248 ms 43240 KB Output is correct
13 Correct 263 ms 45676 KB Output is correct
14 Correct 222 ms 43852 KB Output is correct
15 Correct 5 ms 5376 KB Output is correct
16 Correct 5 ms 5376 KB Output is correct
17 Correct 5 ms 5376 KB Output is correct
18 Correct 4 ms 5280 KB Output is correct
19 Correct 5 ms 5376 KB Output is correct
20 Correct 5 ms 5376 KB Output is correct
21 Correct 6 ms 5376 KB Output is correct
22 Correct 5 ms 5504 KB Output is correct
23 Correct 5 ms 5376 KB Output is correct
24 Correct 23 ms 9656 KB Output is correct
25 Correct 270 ms 43788 KB Output is correct
26 Correct 287 ms 41848 KB Output is correct
27 Correct 273 ms 39916 KB Output is correct
28 Correct 273 ms 38764 KB Output is correct
29 Correct 234 ms 37868 KB Output is correct
30 Correct 213 ms 35180 KB Output is correct
31 Correct 288 ms 43664 KB Output is correct
32 Correct 293 ms 44012 KB Output is correct
33 Correct 226 ms 41708 KB Output is correct
34 Correct 233 ms 39012 KB Output is correct
35 Correct 5 ms 5376 KB Output is correct
36 Correct 5 ms 5376 KB Output is correct
37 Correct 5 ms 5376 KB Output is correct
38 Correct 5 ms 5248 KB Output is correct
39 Correct 5 ms 5248 KB Output is correct
40 Correct 6 ms 5504 KB Output is correct
41 Correct 5 ms 5376 KB Output is correct
42 Correct 5 ms 5504 KB Output is correct
43 Correct 5 ms 5376 KB Output is correct
44 Correct 6 ms 5376 KB Output is correct
45 Correct 247 ms 35684 KB Output is correct
46 Correct 284 ms 41420 KB Output is correct
47 Correct 273 ms 38764 KB Output is correct
48 Correct 234 ms 38440 KB Output is correct
49 Correct 99 ms 14828 KB Output is correct
50 Correct 85 ms 13676 KB Output is correct
51 Correct 177 ms 30408 KB Output is correct
52 Correct 307 ms 45156 KB Output is correct
53 Correct 280 ms 44008 KB Output is correct
54 Correct 341 ms 49128 KB Output is correct
55 Correct 213 ms 42588 KB Output is correct
56 Correct 271 ms 42984 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4992 KB Output is correct
2 Correct 4 ms 5120 KB Output is correct
3 Correct 4 ms 4992 KB Output is correct
4 Correct 4 ms 5248 KB Output is correct
5 Correct 5 ms 5376 KB Output is correct
6 Correct 5 ms 5376 KB Output is correct
7 Correct 5 ms 5408 KB Output is correct
8 Correct 5 ms 5504 KB Output is correct
9 Correct 204 ms 36460 KB Output is correct
10 Correct 257 ms 43756 KB Output is correct
11 Correct 248 ms 43240 KB Output is correct
12 Correct 263 ms 45676 KB Output is correct
13 Correct 222 ms 43852 KB Output is correct
14 Correct 236 ms 36204 KB Output is correct
15 Correct 627 ms 48140 KB Output is correct
16 Correct 599 ms 45932 KB Output is correct
17 Correct 667 ms 50412 KB Output is correct
18 Correct 607 ms 47340 KB Output is correct
19 Correct 382 ms 41140 KB Output is correct
20 Correct 395 ms 42552 KB Output is correct
21 Correct 399 ms 42012 KB Output is correct
22 Correct 380 ms 42432 KB Output is correct
23 Correct 437 ms 42496 KB Output is correct
24 Correct 380 ms 40908 KB Output is correct
25 Correct 408 ms 41968 KB Output is correct
26 Correct 381 ms 40692 KB Output is correct
27 Correct 5 ms 5376 KB Output is correct
28 Correct 5 ms 5376 KB Output is correct
29 Correct 5 ms 5376 KB Output is correct
30 Correct 4 ms 5280 KB Output is correct
31 Correct 5 ms 5376 KB Output is correct
32 Correct 5 ms 5376 KB Output is correct
33 Correct 6 ms 5376 KB Output is correct
34 Correct 5 ms 5504 KB Output is correct
35 Correct 5 ms 5376 KB Output is correct
36 Correct 23 ms 9656 KB Output is correct
37 Correct 270 ms 43788 KB Output is correct
38 Correct 287 ms 41848 KB Output is correct
39 Correct 273 ms 39916 KB Output is correct
40 Correct 273 ms 38764 KB Output is correct
41 Correct 234 ms 37868 KB Output is correct
42 Correct 213 ms 35180 KB Output is correct
43 Correct 288 ms 43664 KB Output is correct
44 Correct 293 ms 44012 KB Output is correct
45 Correct 226 ms 41708 KB Output is correct
46 Correct 233 ms 39012 KB Output is correct
47 Correct 40 ms 9636 KB Output is correct
48 Correct 653 ms 46812 KB Output is correct
49 Correct 722 ms 45036 KB Output is correct
50 Correct 674 ms 43884 KB Output is correct
51 Correct 679 ms 42900 KB Output is correct
52 Correct 583 ms 40300 KB Output is correct
53 Correct 479 ms 32720 KB Output is correct
54 Correct 692 ms 47544 KB Output is correct
55 Correct 683 ms 47596 KB Output is correct
56 Correct 613 ms 46060 KB Output is correct
57 Correct 568 ms 43320 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4992 KB Output is correct
2 Correct 4 ms 4992 KB Output is correct
3 Correct 4 ms 5120 KB Output is correct
4 Correct 4 ms 4992 KB Output is correct
5 Correct 4 ms 5248 KB Output is correct
6 Correct 5 ms 5376 KB Output is correct
7 Correct 5 ms 5376 KB Output is correct
8 Correct 5 ms 5408 KB Output is correct
9 Correct 5 ms 5504 KB Output is correct
10 Correct 204 ms 36460 KB Output is correct
11 Correct 257 ms 43756 KB Output is correct
12 Correct 248 ms 43240 KB Output is correct
13 Correct 263 ms 45676 KB Output is correct
14 Correct 222 ms 43852 KB Output is correct
15 Correct 236 ms 36204 KB Output is correct
16 Correct 627 ms 48140 KB Output is correct
17 Correct 599 ms 45932 KB Output is correct
18 Correct 667 ms 50412 KB Output is correct
19 Correct 607 ms 47340 KB Output is correct
20 Correct 382 ms 41140 KB Output is correct
21 Correct 395 ms 42552 KB Output is correct
22 Correct 399 ms 42012 KB Output is correct
23 Correct 380 ms 42432 KB Output is correct
24 Correct 437 ms 42496 KB Output is correct
25 Correct 380 ms 40908 KB Output is correct
26 Correct 408 ms 41968 KB Output is correct
27 Correct 381 ms 40692 KB Output is correct
28 Correct 5 ms 5376 KB Output is correct
29 Correct 5 ms 5376 KB Output is correct
30 Correct 5 ms 5376 KB Output is correct
31 Correct 4 ms 5280 KB Output is correct
32 Correct 5 ms 5376 KB Output is correct
33 Correct 5 ms 5376 KB Output is correct
34 Correct 6 ms 5376 KB Output is correct
35 Correct 5 ms 5504 KB Output is correct
36 Correct 5 ms 5376 KB Output is correct
37 Correct 23 ms 9656 KB Output is correct
38 Correct 270 ms 43788 KB Output is correct
39 Correct 287 ms 41848 KB Output is correct
40 Correct 273 ms 39916 KB Output is correct
41 Correct 273 ms 38764 KB Output is correct
42 Correct 234 ms 37868 KB Output is correct
43 Correct 213 ms 35180 KB Output is correct
44 Correct 288 ms 43664 KB Output is correct
45 Correct 293 ms 44012 KB Output is correct
46 Correct 226 ms 41708 KB Output is correct
47 Correct 233 ms 39012 KB Output is correct
48 Correct 40 ms 9636 KB Output is correct
49 Correct 653 ms 46812 KB Output is correct
50 Correct 722 ms 45036 KB Output is correct
51 Correct 674 ms 43884 KB Output is correct
52 Correct 679 ms 42900 KB Output is correct
53 Correct 583 ms 40300 KB Output is correct
54 Correct 479 ms 32720 KB Output is correct
55 Correct 692 ms 47544 KB Output is correct
56 Correct 683 ms 47596 KB Output is correct
57 Correct 613 ms 46060 KB Output is correct
58 Correct 568 ms 43320 KB Output is correct
59 Correct 178 ms 16508 KB Output is correct
60 Correct 602 ms 47724 KB Output is correct
61 Correct 611 ms 46552 KB Output is correct
62 Correct 653 ms 49332 KB Output is correct
63 Correct 606 ms 47032 KB Output is correct
64 Correct 5 ms 5376 KB Output is correct
65 Correct 5 ms 5376 KB Output is correct
66 Correct 5 ms 5376 KB Output is correct
67 Correct 5 ms 5248 KB Output is correct
68 Correct 5 ms 5248 KB Output is correct
69 Correct 6 ms 5504 KB Output is correct
70 Correct 5 ms 5376 KB Output is correct
71 Correct 5 ms 5504 KB Output is correct
72 Correct 5 ms 5376 KB Output is correct
73 Correct 6 ms 5376 KB Output is correct
74 Correct 247 ms 35684 KB Output is correct
75 Correct 284 ms 41420 KB Output is correct
76 Correct 273 ms 38764 KB Output is correct
77 Correct 234 ms 38440 KB Output is correct
78 Correct 99 ms 14828 KB Output is correct
79 Correct 85 ms 13676 KB Output is correct
80 Correct 177 ms 30408 KB Output is correct
81 Correct 307 ms 45156 KB Output is correct
82 Correct 280 ms 44008 KB Output is correct
83 Correct 341 ms 49128 KB Output is correct
84 Correct 213 ms 42588 KB Output is correct
85 Correct 271 ms 42984 KB Output is correct
86 Correct 132 ms 17648 KB Output is correct
87 Correct 720 ms 44640 KB Output is correct
88 Correct 726 ms 44524 KB Output is correct
89 Correct 489 ms 40172 KB Output is correct
90 Correct 275 ms 18684 KB Output is correct
91 Correct 288 ms 19940 KB Output is correct
92 Correct 457 ms 33964 KB Output is correct
93 Correct 721 ms 49000 KB Output is correct
94 Correct 599 ms 47844 KB Output is correct
95 Correct 746 ms 52840 KB Output is correct
96 Correct 592 ms 44912 KB Output is correct
97 Correct 579 ms 44900 KB Output is correct