oj.uz

Submission #973054

# Submission time Handle Problem Language Result Execution time Memory
973054 2024-05-01T12:57:56 Z Younis_Dwai Swapping Cities (APIO20_swap) C++14
53 / 100
 278 ms 50356 KB 
#include "swap.h"

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define in insert
#define F first
#define S second
vector<int> adj[200009];
int par1[200009],par[200009][21],depth[200009],cnt[200009],nxt=0,good[200009],val[2000009];
int get_par(int node){
    if(par1[node]==node) return node;
    return par1[node]=get_par(par1[node]);
}
void merg(int u,  int v ,int w){
     int uu=get_par(u);
     int vv=get_par(v);
     nxt++;
     val[nxt]=w;
     if(uu==vv){
        adj[nxt].pb(uu);
        cnt[u]++;
        cnt[v]++;
        good[nxt]=1;
        par1[uu]=nxt;
        return ;
     }
     adj[nxt].pb(uu);
     adj[nxt].pb(vv);
     cnt[u]++;
     cnt[v]++;
     par1[uu]=nxt;
     par1[vv]=nxt;
     if(cnt[u]>=3 || cnt[v]>=3) good[nxt]=1;
     return ;
}
void dfs(int node , int p){
     par[node][0]=p;
     for(int i=1;i<=20;i++) par[node][i]=par[par[node][i-1]][i-1];
     for(auto u : adj[node]){
         depth[u]=1+depth[node];
         dfs(u,node);
         good[node]|=good[u];
     }
     //cout<<" # "<<node<<' '<<good[node]<<' '<<val[node]<<endl;
     return ;
}
void init(int N, int M,std::vector<int> U, std::vector<int> V, std::vector<int> W) {
     nxt=N-1;
     for(int i=0;i<N+M;i++) par1[i]=i;
     vector<pair<int,pair<int,int>>> v;
     for(int i=0;i<M;i++){
         v.pb({W[i],{U[i],V[i]}});
     }
     sort(v.begin(),v.end());
     for(auto u : v){
         merg(u.S.F,u.S.S,u.F);
     }
     dfs(nxt,nxt);
     return ;
}
int lca(int u , int v){
    if(depth[v]>depth[u]) swap(u,v);
    for(int i=20;i>=0;i--) if(depth[u]-(1<<i)>=depth[v]) u=par[u][i];
    if(u==v) return u;
    for(int i=20;i>=0;i--) if(par[u][i]!=par[v][i]) u=par[u][i],v=par[v][i];
    return par[u][0];
}
int getMinimumFuelCapacity(int X, int Y) {
    int lc=lca(X,Y);
    //cout<<" @ "<<X<<' '<<Y<<' '<<lc<<endl;
    if(good[lc]==1) return val[lc];
    for(int i=20;i>=0;i--) if(good[par[lc][i]]==0) lc=par[lc][i];
    lc=par[lc][0];
    if(good[lc]) return val[lc];
    return -1;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9816 KB Output is correct
2 Correct 2 ms 9564 KB Output is correct
3 Correct 3 ms 9564 KB Output is correct
4 Correct 2 ms 9820 KB Output is correct
5 Correct 3 ms 9820 KB Output is correct
6 Correct 2 ms 9820 KB Output is correct
7 Correct 2 ms 9820 KB Output is correct
8 Correct 3 ms 9820 KB Output is correct
9 Correct 73 ms 31696 KB Output is correct
10 Correct 96 ms 34760 KB Output is correct
11 Correct 89 ms 34668 KB Output is correct
12 Correct 102 ms 34984 KB Output is correct
13 Correct 81 ms 38836 KB Output is correct
14 Correct 84 ms 33460 KB Output is correct
15 Correct 207 ms 38596 KB Output is correct
16 Correct 196 ms 38264 KB Output is correct
17 Correct 211 ms 38948 KB Output is correct
18 Correct 256 ms 42800 KB Output is correct
19 Correct 85 ms 22356 KB Output is correct
20 Correct 218 ms 38568 KB Output is correct
21 Correct 224 ms 38964 KB Output is correct
22 Correct 211 ms 39312 KB Output is correct
23 Correct 239 ms 43140 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9816 KB Output is correct
2 Correct 2 ms 9564 KB Output is correct
3 Correct 175 ms 43756 KB Output is correct
4 Correct 183 ms 48016 KB Output is correct
5 Correct 217 ms 48108 KB Output is correct
6 Correct 179 ms 48040 KB Output is correct
7 Correct 189 ms 48060 KB Output is correct
8 Correct 199 ms 47652 KB Output is correct
9 Correct 175 ms 47952 KB Output is correct
10 Correct 175 ms 47416 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9816 KB Output is correct
2 Correct 2 ms 9564 KB Output is correct
3 Correct 3 ms 9564 KB Output is correct
4 Correct 2 ms 9820 KB Output is correct
5 Correct 3 ms 9820 KB Output is correct
6 Correct 2 ms 9820 KB Output is correct
7 Correct 2 ms 9820 KB Output is correct
8 Correct 3 ms 9820 KB Output is correct
9 Correct 2 ms 11612 KB Output is correct
10 Correct 3 ms 11868 KB Output is correct
11 Correct 3 ms 11868 KB Output is correct
12 Correct 3 ms 11868 KB Output is correct
13 Correct 3 ms 11868 KB Output is correct
14 Correct 3 ms 11868 KB Output is correct
15 Correct 3 ms 11868 KB Output is correct
16 Correct 3 ms 11868 KB Output is correct
17 Correct 3 ms 11868 KB Output is correct
18 Correct 3 ms 12120 KB Output is correct
19 Correct 3 ms 11864 KB Output is correct
20 Correct 3 ms 11868 KB Output is correct
21 Correct 3 ms 11868 KB Output is correct
22 Correct 3 ms 11924 KB Output is correct
23 Correct 3 ms 11868 KB Output is correct
24 Correct 3 ms 11868 KB Output is correct
25 Correct 3 ms 11868 KB Output is correct
26 Correct 3 ms 11868 KB Output is correct
27 Correct 3 ms 11868 KB Output is correct
28 Correct 3 ms 11868 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11612 KB Output is correct
2 Correct 3 ms 9816 KB Output is correct
3 Correct 2 ms 9564 KB Output is correct
4 Correct 3 ms 9564 KB Output is correct
5 Correct 2 ms 9820 KB Output is correct
6 Correct 3 ms 9820 KB Output is correct
7 Correct 2 ms 9820 KB Output is correct
8 Correct 2 ms 9820 KB Output is correct
9 Correct 3 ms 9820 KB Output is correct
10 Correct 73 ms 31696 KB Output is correct
11 Correct 96 ms 34760 KB Output is correct
12 Correct 89 ms 34668 KB Output is correct
13 Correct 102 ms 34984 KB Output is correct
14 Correct 81 ms 38836 KB Output is correct
15 Correct 3 ms 11868 KB Output is correct
16 Correct 3 ms 11868 KB Output is correct
17 Correct 3 ms 11868 KB Output is correct
18 Correct 3 ms 11868 KB Output is correct
19 Correct 3 ms 11868 KB Output is correct
20 Correct 3 ms 11868 KB Output is correct
21 Correct 3 ms 11868 KB Output is correct
22 Correct 3 ms 11868 KB Output is correct
23 Correct 3 ms 12120 KB Output is correct
24 Correct 3 ms 11864 KB Output is correct
25 Correct 3 ms 11868 KB Output is correct
26 Correct 3 ms 11868 KB Output is correct
27 Correct 3 ms 11924 KB Output is correct
28 Correct 3 ms 11868 KB Output is correct
29 Correct 3 ms 11868 KB Output is correct
30 Correct 3 ms 11868 KB Output is correct
31 Correct 3 ms 11868 KB Output is correct
32 Correct 3 ms 11868 KB Output is correct
33 Correct 3 ms 11868 KB Output is correct
34 Correct 11 ms 15128 KB Output is correct
35 Correct 117 ms 36552 KB Output is correct
36 Correct 100 ms 36528 KB Output is correct
37 Correct 101 ms 36528 KB Output is correct
38 Correct 103 ms 36392 KB Output is correct
39 Correct 107 ms 36552 KB Output is correct
40 Correct 87 ms 35780 KB Output is correct
41 Correct 101 ms 35012 KB Output is correct
42 Correct 100 ms 34756 KB Output is correct
43 Correct 84 ms 41672 KB Output is correct
44 Correct 100 ms 36916 KB Output is correct
45 Runtime error 107 ms 50356 KB Execution killed with signal 11
46 Halted 0 ms 0 KB -

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9816 KB Output is correct
2 Correct 2 ms 9564 KB Output is correct
3 Correct 3 ms 9564 KB Output is correct
4 Correct 2 ms 9820 KB Output is correct
5 Correct 3 ms 9820 KB Output is correct
6 Correct 2 ms 9820 KB Output is correct
7 Correct 2 ms 9820 KB Output is correct
8 Correct 3 ms 9820 KB Output is correct
9 Correct 73 ms 31696 KB Output is correct
10 Correct 96 ms 34760 KB Output is correct
11 Correct 89 ms 34668 KB Output is correct
12 Correct 102 ms 34984 KB Output is correct
13 Correct 81 ms 38836 KB Output is correct
14 Correct 84 ms 33460 KB Output is correct
15 Correct 207 ms 38596 KB Output is correct
16 Correct 196 ms 38264 KB Output is correct
17 Correct 211 ms 38948 KB Output is correct
18 Correct 256 ms 42800 KB Output is correct
19 Correct 175 ms 43756 KB Output is correct
20 Correct 183 ms 48016 KB Output is correct
21 Correct 217 ms 48108 KB Output is correct
22 Correct 179 ms 48040 KB Output is correct
23 Correct 189 ms 48060 KB Output is correct
24 Correct 199 ms 47652 KB Output is correct
25 Correct 175 ms 47952 KB Output is correct
26 Correct 175 ms 47416 KB Output is correct
27 Correct 3 ms 11868 KB Output is correct
28 Correct 3 ms 11868 KB Output is correct
29 Correct 3 ms 11868 KB Output is correct
30 Correct 3 ms 11868 KB Output is correct
31 Correct 3 ms 11868 KB Output is correct
32 Correct 3 ms 11868 KB Output is correct
33 Correct 3 ms 11868 KB Output is correct
34 Correct 3 ms 11868 KB Output is correct
35 Correct 3 ms 12120 KB Output is correct
36 Correct 11 ms 15128 KB Output is correct
37 Correct 117 ms 36552 KB Output is correct
38 Correct 100 ms 36528 KB Output is correct
39 Correct 101 ms 36528 KB Output is correct
40 Correct 103 ms 36392 KB Output is correct
41 Correct 107 ms 36552 KB Output is correct
42 Correct 87 ms 35780 KB Output is correct
43 Correct 101 ms 35012 KB Output is correct
44 Correct 100 ms 34756 KB Output is correct
45 Correct 84 ms 41672 KB Output is correct
46 Correct 100 ms 36916 KB Output is correct
47 Correct 18 ms 15240 KB Output is correct
48 Correct 197 ms 40388 KB Output is correct
49 Correct 191 ms 40516 KB Output is correct
50 Correct 211 ms 40652 KB Output is correct
51 Correct 221 ms 40392 KB Output is correct
52 Correct 218 ms 40012 KB Output is correct
53 Correct 162 ms 36912 KB Output is correct
54 Correct 233 ms 39316 KB Output is correct
55 Correct 247 ms 38548 KB Output is correct
56 Correct 278 ms 44488 KB Output is correct
57 Correct 226 ms 41344 KB Output is correct

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11612 KB Output is correct
2 Correct 3 ms 9816 KB Output is correct
3 Correct 2 ms 9564 KB Output is correct
4 Correct 3 ms 9564 KB Output is correct
5 Correct 2 ms 9820 KB Output is correct
6 Correct 3 ms 9820 KB Output is correct
7 Correct 2 ms 9820 KB Output is correct
8 Correct 2 ms 9820 KB Output is correct
9 Correct 3 ms 9820 KB Output is correct
10 Correct 73 ms 31696 KB Output is correct
11 Correct 96 ms 34760 KB Output is correct
12 Correct 89 ms 34668 KB Output is correct
13 Correct 102 ms 34984 KB Output is correct
14 Correct 81 ms 38836 KB Output is correct
15 Correct 84 ms 33460 KB Output is correct
16 Correct 207 ms 38596 KB Output is correct
17 Correct 196 ms 38264 KB Output is correct
18 Correct 211 ms 38948 KB Output is correct
19 Correct 256 ms 42800 KB Output is correct
20 Correct 175 ms 43756 KB Output is correct
21 Correct 183 ms 48016 KB Output is correct
22 Correct 217 ms 48108 KB Output is correct
23 Correct 179 ms 48040 KB Output is correct
24 Correct 189 ms 48060 KB Output is correct
25 Correct 199 ms 47652 KB Output is correct
26 Correct 175 ms 47952 KB Output is correct
27 Correct 175 ms 47416 KB Output is correct
28 Correct 3 ms 11868 KB Output is correct
29 Correct 3 ms 11868 KB Output is correct
30 Correct 3 ms 11868 KB Output is correct
31 Correct 3 ms 11868 KB Output is correct
32 Correct 3 ms 11868 KB Output is correct
33 Correct 3 ms 11868 KB Output is correct
34 Correct 3 ms 11868 KB Output is correct
35 Correct 3 ms 11868 KB Output is correct
36 Correct 3 ms 12120 KB Output is correct
37 Correct 11 ms 15128 KB Output is correct
38 Correct 117 ms 36552 KB Output is correct
39 Correct 100 ms 36528 KB Output is correct
40 Correct 101 ms 36528 KB Output is correct
41 Correct 103 ms 36392 KB Output is correct
42 Correct 107 ms 36552 KB Output is correct
43 Correct 87 ms 35780 KB Output is correct
44 Correct 101 ms 35012 KB Output is correct
45 Correct 100 ms 34756 KB Output is correct
46 Correct 84 ms 41672 KB Output is correct
47 Correct 100 ms 36916 KB Output is correct
48 Correct 18 ms 15240 KB Output is correct
49 Correct 197 ms 40388 KB Output is correct
50 Correct 191 ms 40516 KB Output is correct
51 Correct 211 ms 40652 KB Output is correct
52 Correct 221 ms 40392 KB Output is correct
53 Correct 218 ms 40012 KB Output is correct
54 Correct 162 ms 36912 KB Output is correct
55 Correct 233 ms 39316 KB Output is correct
56 Correct 247 ms 38548 KB Output is correct
57 Correct 278 ms 44488 KB Output is correct
58 Correct 226 ms 41344 KB Output is correct
59 Correct 85 ms 22356 KB Output is correct
60 Correct 218 ms 38568 KB Output is correct
61 Correct 224 ms 38964 KB Output is correct
62 Correct 211 ms 39312 KB Output is correct
63 Correct 239 ms 43140 KB Output is correct
64 Correct 3 ms 11864 KB Output is correct
65 Correct 3 ms 11868 KB Output is correct
66 Correct 3 ms 11868 KB Output is correct
67 Correct 3 ms 11924 KB Output is correct
68 Correct 3 ms 11868 KB Output is correct
69 Correct 3 ms 11868 KB Output is correct
70 Correct 3 ms 11868 KB Output is correct
71 Correct 3 ms 11868 KB Output is correct
72 Correct 3 ms 11868 KB Output is correct
73 Correct 3 ms 11868 KB Output is correct
74 Runtime error 107 ms 50356 KB Execution killed with signal 11
75 Halted 0 ms 0 KB -