oj.uz

Submission #1055255

# Submission time Handle Problem Language Result Execution time Memory
1055255 2024-08-12T16:00:56 Z alexander707070 Swapping Cities (APIO20_swap) C++14
100 / 100
 600 ms 65272 KB 
#include<bits/stdc++.h>
#include "swap.h"

#define MAXN 200007
using namespace std;

const int inf=1e9+7;

int n,m;

struct edge{
    int from,to,cost;
    
    inline friend bool operator < (edge fr,edge sc){
        return fr.cost<sc.cost;
    }
}e[MAXN];

int closest[MAXN],special[MAXN],parent[MAXN];
int lt[MAXN],rt[MAXN],in[MAXN],out[MAXN],num;
vector<int> query[MAXN];
vector<int> tree[MAXN],edges;
bool treeedge[MAXN];

struct union_find{
    vector< pair<int,int> > dsu[MAXN];

    int sz[MAXN],trip[MAXN],deg[MAXN],tim,topv[MAXN];

    void reset(){
        for(int i=1;i<=n;i++){
            dsu[i]={{i,0}}; sz[i]=1; trip[i]=deg[i]=0;
            topv[i]=i;
        }
        tim=0;
    }

    int root(int x){
        if(dsu[x].back().first==x)return dsu[x].back().first;
        return root(dsu[x].back().first);
    }

    void mergev(int x,int y){
        tim++;

        int rootx=root(x);
        int rooty=root(y);

        deg[x]++; deg[y]++;

        if(deg[x]>=3)trip[rootx]=x;
        if(deg[y]>=3)trip[rootx]=y;

        if(rootx==rooty)return;
        if(sz[rootx]<sz[rooty])swap(rootx,rooty);

        dsu[rooty].push_back({rootx,tim});
        sz[rootx]+=sz[rooty];
        if(trip[rooty]!=0)trip[rootx]=trip[rooty];

        if(in[topv[rooty]]<in[topv[rootx]])topv[rootx]=topv[rooty];
    }

    int comp(int x,int when){
        int l=0,r=dsu[x].size(),tt;

        while(l+1<r){
            tt=(l+r)/2;
            if(dsu[x][tt].second<=when){
                l=tt;
            }else{
                r=tt;
            }
        }

        return dsu[x][l].first;
    }

    int pastroot(int x,int when){
        int curr=comp(x,when);

        if(curr==x)return x;
        return pastroot(curr,when);
    }
}graph,bcc;

void build_mst(){
    graph.reset();

    for(int i=1;i<=m;i++){
        graph.mergev(e[i].from,e[i].to);

        for(int f:query[i]){
            closest[f]=graph.trip[graph.root(f)];
        }
    }
}

void dfs(int x,int p){
    parent[x]=p;
    num++; in[x]=num;

    for(int i:tree[x]){
        if(i==p)continue;
        dfs(i,x);
    }

    out[x]=num;
}

bool subtree(int x,int y){
    return in[y]>=in[x] and out[y]<=out[x];
}

void init(int N, int M,vector<int> U, vector<int> V, vector<int> W) {
    
    n=N; m=M;
    for(int i=1;i<=m;i++){
        e[i]={U[i-1]+1,V[i-1]+1,W[i-1]};
    }

    sort(e+1,e+m+1);

    for(int i=1;i<=n;i++){
        lt[i]=0; rt[i]=m+1;
    }

    for(int i=1;i<=18;i++){
        for(int f=1;f<=m;f++)query[f].clear();

        for(int f=1;f<=n;f++){
            query[(lt[f]+rt[f])/2].push_back(f);
        }

        build_mst();

        for(int f=1;f<=n;f++){
            if(closest[f]!=0){
                rt[f]=(lt[f]+rt[f])/2;
                special[f]=closest[f];
            }else{
                lt[f]=(lt[f]+rt[f])/2;
            }
        }
    }

    bcc.reset();
    for(int i=1;i<=m;i++){
        if(bcc.root(e[i].from)==bcc.root(e[i].to))continue;

        tree[e[i].from].push_back(e[i].to);
        tree[e[i].to].push_back(e[i].from);

        bcc.mergev(e[i].from,e[i].to);
        treeedge[i]=true;
    }

    dfs(1,0);

    bcc.reset();
    for(int i=1;i<=m;i++){
        if(treeedge[i])continue;

        int x=bcc.root(e[i].from),y=bcc.root(e[i].to);
        while(!subtree(bcc.topv[x],bcc.topv[y])){
            bcc.mergev(x,bcc.root(parent[bcc.topv[x]]));
            x=bcc.root(x);

            bcc.tim--;
        }

        while(bcc.root(x)!=bcc.root(y)){
            bcc.mergev(y,bcc.root(parent[bcc.topv[y]]));
            y=bcc.root(y);

            bcc.tim--;
        }

        bcc.tim++;

        edges.push_back(e[i].cost);
    }
}

int getMinimumFuelCapacity(int X, int Y){
    X++; Y++;
    int ans=inf;

    if(rt[X]<=m){
        ans=e[max(rt[X],rt[Y])].cost;
    }

    int l=0,r=edges.size()+1,tt;
    while(l+1<r){
        tt=(l+r)/2;
        if(bcc.pastroot(X,tt)==bcc.pastroot(Y,tt)){
            r=tt;
        }else{
            l=tt;
        }
    }

    if(r!=edges.size()+1)ans=min(ans,edges[r-1]);

    l=0; r=m+1;
    while(l+1<r){
        tt=(l+r)/2;
        if(graph.pastroot(X,tt)==graph.pastroot(Y,tt)){
            r=tt;
        }else{
            l=tt;
        }
    }

    ans=max(ans,e[r].cost);

    if(ans==inf)return -1;

    return ans;
}

/*
int main(){
    init(5,5,{0,1,2,3,4},{1,2,3,4,0},{1,2,3,4,5});

    cout<<getMinimumFuelCapacity(0,2)<<"\n";
    cout<<getMinimumFuelCapacity(1,3)<<"\n";
    cout<<getMinimumFuelCapacity(3,4)<<"\n";
}
*/

Compilation message

swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:203:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  203 |     if(r!=edges.size()+1)ans=min(ans,edges[r-1]);
      |        ~^~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 31324 KB Output is correct
2 Correct 3 ms 31324 KB Output is correct
3 Correct 3 ms 31324 KB Output is correct
4 Correct 4 ms 31324 KB Output is correct
5 Correct 5 ms 31324 KB Output is correct
6 Correct 4 ms 31364 KB Output is correct
7 Correct 4 ms 31408 KB Output is correct
8 Correct 4 ms 31580 KB Output is correct
9 Correct 142 ms 49992 KB Output is correct
10 Correct 176 ms 54476 KB Output is correct
11 Correct 168 ms 54024 KB Output is correct
12 Correct 185 ms 55308 KB Output is correct
13 Correct 142 ms 56588 KB Output is correct
14 Correct 160 ms 49672 KB Output is correct
15 Correct 334 ms 56408 KB Output is correct
16 Correct 338 ms 54904 KB Output is correct
17 Correct 347 ms 58224 KB Output is correct
18 Correct 197 ms 57196 KB Output is correct
19 Correct 124 ms 38212 KB Output is correct
20 Correct 352 ms 61412 KB Output is correct
21 Correct 332 ms 60292 KB Output is correct
22 Correct 363 ms 62512 KB Output is correct
23 Correct 219 ms 62772 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 31324 KB Output is correct
2 Correct 3 ms 31324 KB Output is correct
3 Correct 199 ms 57628 KB Output is correct
4 Correct 210 ms 58456 KB Output is correct
5 Correct 238 ms 57952 KB Output is correct
6 Correct 218 ms 58160 KB Output is correct
7 Correct 233 ms 58224 KB Output is correct
8 Correct 224 ms 57672 KB Output is correct
9 Correct 222 ms 57964 KB Output is correct
10 Correct 210 ms 57368 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 31324 KB Output is correct
2 Correct 3 ms 31324 KB Output is correct
3 Correct 3 ms 31324 KB Output is correct
4 Correct 4 ms 31324 KB Output is correct
5 Correct 5 ms 31324 KB Output is correct
6 Correct 4 ms 31364 KB Output is correct
7 Correct 4 ms 31408 KB Output is correct
8 Correct 4 ms 31580 KB Output is correct
9 Correct 4 ms 31324 KB Output is correct
10 Correct 5 ms 31324 KB Output is correct
11 Correct 4 ms 31408 KB Output is correct
12 Correct 4 ms 31324 KB Output is correct
13 Correct 7 ms 31548 KB Output is correct
14 Correct 5 ms 31324 KB Output is correct
15 Correct 5 ms 31324 KB Output is correct
16 Correct 6 ms 31324 KB Output is correct
17 Correct 5 ms 31580 KB Output is correct
18 Correct 4 ms 31412 KB Output is correct
19 Correct 4 ms 31324 KB Output is correct
20 Correct 4 ms 31492 KB Output is correct
21 Correct 5 ms 31324 KB Output is correct
22 Correct 5 ms 31376 KB Output is correct
23 Correct 5 ms 31324 KB Output is correct
24 Correct 7 ms 31432 KB Output is correct
25 Correct 5 ms 31592 KB Output is correct
26 Correct 5 ms 31580 KB Output is correct
27 Correct 5 ms 31580 KB Output is correct
28 Correct 6 ms 31580 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 31324 KB Output is correct
2 Correct 4 ms 31324 KB Output is correct
3 Correct 3 ms 31324 KB Output is correct
4 Correct 3 ms 31324 KB Output is correct
5 Correct 4 ms 31324 KB Output is correct
6 Correct 5 ms 31324 KB Output is correct
7 Correct 4 ms 31364 KB Output is correct
8 Correct 4 ms 31408 KB Output is correct
9 Correct 4 ms 31580 KB Output is correct
10 Correct 142 ms 49992 KB Output is correct
11 Correct 176 ms 54476 KB Output is correct
12 Correct 168 ms 54024 KB Output is correct
13 Correct 185 ms 55308 KB Output is correct
14 Correct 142 ms 56588 KB Output is correct
15 Correct 5 ms 31324 KB Output is correct
16 Correct 4 ms 31408 KB Output is correct
17 Correct 4 ms 31324 KB Output is correct
18 Correct 7 ms 31548 KB Output is correct
19 Correct 5 ms 31324 KB Output is correct
20 Correct 5 ms 31324 KB Output is correct
21 Correct 6 ms 31324 KB Output is correct
22 Correct 5 ms 31580 KB Output is correct
23 Correct 4 ms 31412 KB Output is correct
24 Correct 4 ms 31324 KB Output is correct
25 Correct 4 ms 31492 KB Output is correct
26 Correct 5 ms 31324 KB Output is correct
27 Correct 5 ms 31376 KB Output is correct
28 Correct 5 ms 31324 KB Output is correct
29 Correct 7 ms 31432 KB Output is correct
30 Correct 5 ms 31592 KB Output is correct
31 Correct 5 ms 31580 KB Output is correct
32 Correct 5 ms 31580 KB Output is correct
33 Correct 6 ms 31580 KB Output is correct
34 Correct 29 ms 34120 KB Output is correct
35 Correct 184 ms 55268 KB Output is correct
36 Correct 189 ms 54000 KB Output is correct
37 Correct 180 ms 53352 KB Output is correct
38 Correct 179 ms 53344 KB Output is correct
39 Correct 175 ms 53848 KB Output is correct
40 Correct 160 ms 52680 KB Output is correct
41 Correct 180 ms 53872 KB Output is correct
42 Correct 180 ms 54540 KB Output is correct
43 Correct 155 ms 58828 KB Output is correct
44 Correct 185 ms 55244 KB Output is correct
45 Correct 252 ms 53708 KB Output is correct
46 Correct 188 ms 53224 KB Output is correct
47 Correct 175 ms 53692 KB Output is correct
48 Correct 197 ms 55496 KB Output is correct
49 Correct 101 ms 38360 KB Output is correct
50 Correct 99 ms 38360 KB Output is correct
51 Correct 208 ms 49956 KB Output is correct
52 Correct 302 ms 55172 KB Output is correct
53 Correct 259 ms 57036 KB Output is correct
54 Correct 373 ms 57420 KB Output is correct
55 Correct 151 ms 59548 KB Output is correct
56 Correct 293 ms 58484 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 31324 KB Output is correct
2 Correct 3 ms 31324 KB Output is correct
3 Correct 3 ms 31324 KB Output is correct
4 Correct 4 ms 31324 KB Output is correct
5 Correct 5 ms 31324 KB Output is correct
6 Correct 4 ms 31364 KB Output is correct
7 Correct 4 ms 31408 KB Output is correct
8 Correct 4 ms 31580 KB Output is correct
9 Correct 142 ms 49992 KB Output is correct
10 Correct 176 ms 54476 KB Output is correct
11 Correct 168 ms 54024 KB Output is correct
12 Correct 185 ms 55308 KB Output is correct
13 Correct 142 ms 56588 KB Output is correct
14 Correct 160 ms 49672 KB Output is correct
15 Correct 334 ms 56408 KB Output is correct
16 Correct 338 ms 54904 KB Output is correct
17 Correct 347 ms 58224 KB Output is correct
18 Correct 197 ms 57196 KB Output is correct
19 Correct 199 ms 57628 KB Output is correct
20 Correct 210 ms 58456 KB Output is correct
21 Correct 238 ms 57952 KB Output is correct
22 Correct 218 ms 58160 KB Output is correct
23 Correct 233 ms 58224 KB Output is correct
24 Correct 224 ms 57672 KB Output is correct
25 Correct 222 ms 57964 KB Output is correct
26 Correct 210 ms 57368 KB Output is correct
27 Correct 5 ms 31324 KB Output is correct
28 Correct 4 ms 31408 KB Output is correct
29 Correct 4 ms 31324 KB Output is correct
30 Correct 7 ms 31548 KB Output is correct
31 Correct 5 ms 31324 KB Output is correct
32 Correct 5 ms 31324 KB Output is correct
33 Correct 6 ms 31324 KB Output is correct
34 Correct 5 ms 31580 KB Output is correct
35 Correct 4 ms 31412 KB Output is correct
36 Correct 29 ms 34120 KB Output is correct
37 Correct 184 ms 55268 KB Output is correct
38 Correct 189 ms 54000 KB Output is correct
39 Correct 180 ms 53352 KB Output is correct
40 Correct 179 ms 53344 KB Output is correct
41 Correct 175 ms 53848 KB Output is correct
42 Correct 160 ms 52680 KB Output is correct
43 Correct 180 ms 53872 KB Output is correct
44 Correct 180 ms 54540 KB Output is correct
45 Correct 155 ms 58828 KB Output is correct
46 Correct 185 ms 55244 KB Output is correct
47 Correct 36 ms 34128 KB Output is correct
48 Correct 340 ms 56680 KB Output is correct
49 Correct 344 ms 56256 KB Output is correct
50 Correct 326 ms 56268 KB Output is correct
51 Correct 323 ms 56308 KB Output is correct
52 Correct 311 ms 55776 KB Output is correct
53 Correct 252 ms 50876 KB Output is correct
54 Correct 341 ms 56676 KB Output is correct
55 Correct 332 ms 56688 KB Output is correct
56 Correct 232 ms 61712 KB Output is correct
57 Correct 319 ms 58420 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 31324 KB Output is correct
2 Correct 4 ms 31324 KB Output is correct
3 Correct 3 ms 31324 KB Output is correct
4 Correct 3 ms 31324 KB Output is correct
5 Correct 4 ms 31324 KB Output is correct
6 Correct 5 ms 31324 KB Output is correct
7 Correct 4 ms 31364 KB Output is correct
8 Correct 4 ms 31408 KB Output is correct
9 Correct 4 ms 31580 KB Output is correct
10 Correct 142 ms 49992 KB Output is correct
11 Correct 176 ms 54476 KB Output is correct
12 Correct 168 ms 54024 KB Output is correct
13 Correct 185 ms 55308 KB Output is correct
14 Correct 142 ms 56588 KB Output is correct
15 Correct 160 ms 49672 KB Output is correct
16 Correct 334 ms 56408 KB Output is correct
17 Correct 338 ms 54904 KB Output is correct
18 Correct 347 ms 58224 KB Output is correct
19 Correct 197 ms 57196 KB Output is correct
20 Correct 199 ms 57628 KB Output is correct
21 Correct 210 ms 58456 KB Output is correct
22 Correct 238 ms 57952 KB Output is correct
23 Correct 218 ms 58160 KB Output is correct
24 Correct 233 ms 58224 KB Output is correct
25 Correct 224 ms 57672 KB Output is correct
26 Correct 222 ms 57964 KB Output is correct
27 Correct 210 ms 57368 KB Output is correct
28 Correct 5 ms 31324 KB Output is correct
29 Correct 4 ms 31408 KB Output is correct
30 Correct 4 ms 31324 KB Output is correct
31 Correct 7 ms 31548 KB Output is correct
32 Correct 5 ms 31324 KB Output is correct
33 Correct 5 ms 31324 KB Output is correct
34 Correct 6 ms 31324 KB Output is correct
35 Correct 5 ms 31580 KB Output is correct
36 Correct 4 ms 31412 KB Output is correct
37 Correct 29 ms 34120 KB Output is correct
38 Correct 184 ms 55268 KB Output is correct
39 Correct 189 ms 54000 KB Output is correct
40 Correct 180 ms 53352 KB Output is correct
41 Correct 179 ms 53344 KB Output is correct
42 Correct 175 ms 53848 KB Output is correct
43 Correct 160 ms 52680 KB Output is correct
44 Correct 180 ms 53872 KB Output is correct
45 Correct 180 ms 54540 KB Output is correct
46 Correct 155 ms 58828 KB Output is correct
47 Correct 185 ms 55244 KB Output is correct
48 Correct 36 ms 34128 KB Output is correct
49 Correct 340 ms 56680 KB Output is correct
50 Correct 344 ms 56256 KB Output is correct
51 Correct 326 ms 56268 KB Output is correct
52 Correct 323 ms 56308 KB Output is correct
53 Correct 311 ms 55776 KB Output is correct
54 Correct 252 ms 50876 KB Output is correct
55 Correct 341 ms 56676 KB Output is correct
56 Correct 332 ms 56688 KB Output is correct
57 Correct 232 ms 61712 KB Output is correct
58 Correct 319 ms 58420 KB Output is correct
59 Correct 124 ms 38212 KB Output is correct
60 Correct 352 ms 61412 KB Output is correct
61 Correct 332 ms 60292 KB Output is correct
62 Correct 363 ms 62512 KB Output is correct
63 Correct 219 ms 62772 KB Output is correct
64 Correct 4 ms 31324 KB Output is correct
65 Correct 4 ms 31492 KB Output is correct
66 Correct 5 ms 31324 KB Output is correct
67 Correct 5 ms 31376 KB Output is correct
68 Correct 5 ms 31324 KB Output is correct
69 Correct 7 ms 31432 KB Output is correct
70 Correct 5 ms 31592 KB Output is correct
71 Correct 5 ms 31580 KB Output is correct
72 Correct 5 ms 31580 KB Output is correct
73 Correct 6 ms 31580 KB Output is correct
74 Correct 252 ms 53708 KB Output is correct
75 Correct 188 ms 53224 KB Output is correct
76 Correct 175 ms 53692 KB Output is correct
77 Correct 197 ms 55496 KB Output is correct
78 Correct 101 ms 38360 KB Output is correct
79 Correct 99 ms 38360 KB Output is correct
80 Correct 208 ms 49956 KB Output is correct
81 Correct 302 ms 55172 KB Output is correct
82 Correct 259 ms 57036 KB Output is correct
83 Correct 373 ms 57420 KB Output is correct
84 Correct 151 ms 59548 KB Output is correct
85 Correct 293 ms 58484 KB Output is correct
86 Correct 118 ms 42832 KB Output is correct
87 Correct 354 ms 60056 KB Output is correct
88 Correct 356 ms 60632 KB Output is correct
89 Correct 336 ms 60964 KB Output is correct
90 Correct 240 ms 45184 KB Output is correct
91 Correct 275 ms 47348 KB Output is correct
92 Correct 344 ms 57252 KB Output is correct
93 Correct 542 ms 64440 KB Output is correct
94 Correct 471 ms 65136 KB Output is correct
95 Correct 600 ms 65272 KB Output is correct
96 Correct 244 ms 64840 KB Output is correct
97 Correct 414 ms 65036 KB Output is correct