oj.uz

Submission #982651

# Submission time Handle Problem Language Result Execution time Memory
982651 2024-05-14T15:01:54 Z dimashhh Swapping Cities (APIO20_swap) C++17
6 / 100
 203 ms 54120 KB 
#include "swap.h"

#include <vector>
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+12;

vector<pair<int,int>> g[N];
vector<int> gr[N],st[N];
int n,m,p[N],timer=0,t[N],e1[N],e2[N],first_time[N];
bool is[N];
int get(int v){
    if(p[v] == v) return v;
    return p[v] = get(p[v]);
}
int n1,tt[N],P[N];
void merge(int a,int b){
    int vv,uu;
    vv = a;
    uu = b;
    a = get(a);
    b = get(b);
    if(a == b){
        if(!is[a]){
            for(int j:st[a]){
                first_time[j]=timer;
            }
            st[a].clear();
            is[a]=1;
        }
        timer++;
        return;
    }
    if((int)st[a].size() > (int)st[b].size()){
        swap(vv,uu);
        swap(a, b);
    }
    n1++;
    tt[n1] = timer;
//    cout << n1 << ' ' << P[a] << ' ' << P[b] << "x\n";
    gr[n1].push_back(P[a]);
    gr[n1].push_back(P[b]);
    P[P[a]] = n1;
    P[P[b]] = n1;
    p[a] = b;
    for(int j:st[a]){
        st[b].push_back(j);
    }
    st[a].clear();
    if(is[b] || is[a] || (vv != e1[a] && vv != e2[a]) || (uu != e1[b] && uu != e2[b])) {
        is[b]=1;
        for(int j:st[b]){
            first_time[j]=timer;
        }
        st[b].clear();
    }else{
        if(uu == e1[b]){
            e1[b] = (vv == e1[a] ? e2[a] : e1[a]);
        }else{
            e2[b] = (vv == e1[a] ? e2[a] : e1[a]);
        }
    }
    timer++;
}
int B = 20;
int up[N][20],tin[N],tout[N],tv;
void dfs(int v,int pr){
    up[v][0] = pr;
    tin[v] = tv++;
    for(int i = 1;i < B;i++){
        up[v][i] = up[up[v][i - 1]][i - 1];
    }
    for(int to:gr[v]){
        dfs(to,v);
    }
    tout[v] = tv++;
}
bool is_pr(int a,int b){
    return (tin[a] <= tin[b] && tout[a] >= tout[b]);
}
int lca(int v,int u){
    if(is_pr(v,u)) return v;
    if(is_pr(u,v)) return u;
    for(int i = B - 1;i >= 0;i--){
        if(!is_pr(up[v][i],u)){
            v = up[v][i];
        }
    }
    return up[v][0];
}
vector <array<int, 3>> e;
void init(int nn, int mm,std::vector<int> u, std::vector<int> v, std::vector<int> w) {
    memset(first_time,-1,sizeof(first_time));
    n1 = n = nn;
    m = mm;
    for (int i = 1; i <= m; i++) {
        e.push_back({w[i - 1], u[i - 1] + 1, v[i - 1] + 1});
    }
    sort(e.begin(), e.end());
    for(int i = 1;i <= n;i++) {
        P[i] =e1[i] = e2[i] = p[i] = i;
        st[i].push_back(i);
    }
    for(auto [w,a,b]:e){
        merge(a,b);
    }
    dfs(n1,n1);
}
void merge1(int a,int b){
    a = get(a);
    b = get(b);
    p[a] = b;
}
int getMinimumFuelCapacity(int X, int Y) {
    X++;Y++;
    int f = max(first_time[X],max(tt[lca(X,Y)],first_time[Y]));
    if(first_time[X] == -1 || first_time[Y] == -1) return -1;
//    for(int i = 1;i <= n;i++){
//        p[i] = i;
//    }
//    for(int j = 0;j < m;j++){
//        int vv = e[j][2],uu = e[j][1];
//        merge1(vv,uu);
//        if(get(X) == get(Y)){
//            f = max(f,j);
//            break;
//        }
//    }
    return e[f][0];
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 22876 KB Output is correct
2 Correct 6 ms 22876 KB Output is correct
3 Correct 6 ms 22876 KB Output is correct
4 Correct 5 ms 22876 KB Output is correct
5 Correct 5 ms 22872 KB Output is correct
6 Correct 5 ms 22876 KB Output is correct
7 Correct 5 ms 22960 KB Output is correct
8 Correct 5 ms 22876 KB Output is correct
9 Correct 53 ms 43716 KB Output is correct
10 Correct 58 ms 43464 KB Output is correct
11 Correct 72 ms 45484 KB Output is correct
12 Correct 60 ms 42180 KB Output is correct
13 Correct 68 ms 39640 KB Output is correct
14 Correct 57 ms 43720 KB Output is correct
15 Correct 99 ms 43872 KB Output is correct
16 Correct 100 ms 47712 KB Output is correct
17 Correct 102 ms 42028 KB Output is correct
18 Correct 93 ms 41680 KB Output is correct
19 Correct 48 ms 30228 KB Output is correct
20 Correct 106 ms 46896 KB Output is correct
21 Correct 100 ms 48716 KB Output is correct
22 Correct 107 ms 45660 KB Output is correct
23 Correct 96 ms 42796 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 22876 KB Output is correct
2 Correct 6 ms 22876 KB Output is correct
3 Incorrect 203 ms 54120 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 22876 KB Output is correct
2 Correct 6 ms 22876 KB Output is correct
3 Correct 6 ms 22876 KB Output is correct
4 Correct 5 ms 22876 KB Output is correct
5 Correct 5 ms 22872 KB Output is correct
6 Correct 5 ms 22876 KB Output is correct
7 Correct 5 ms 22960 KB Output is correct
8 Correct 5 ms 22876 KB Output is correct
9 Correct 5 ms 22876 KB Output is correct
10 Incorrect 5 ms 22876 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 22876 KB Output is correct
2 Correct 5 ms 22876 KB Output is correct
3 Correct 6 ms 22876 KB Output is correct
4 Correct 6 ms 22876 KB Output is correct
5 Correct 5 ms 22876 KB Output is correct
6 Correct 5 ms 22872 KB Output is correct
7 Correct 5 ms 22876 KB Output is correct
8 Correct 5 ms 22960 KB Output is correct
9 Correct 5 ms 22876 KB Output is correct
10 Correct 53 ms 43716 KB Output is correct
11 Correct 58 ms 43464 KB Output is correct
12 Correct 72 ms 45484 KB Output is correct
13 Correct 60 ms 42180 KB Output is correct
14 Correct 68 ms 39640 KB Output is correct
15 Incorrect 5 ms 22876 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 22876 KB Output is correct
2 Correct 6 ms 22876 KB Output is correct
3 Correct 6 ms 22876 KB Output is correct
4 Correct 5 ms 22876 KB Output is correct
5 Correct 5 ms 22872 KB Output is correct
6 Correct 5 ms 22876 KB Output is correct
7 Correct 5 ms 22960 KB Output is correct
8 Correct 5 ms 22876 KB Output is correct
9 Correct 53 ms 43716 KB Output is correct
10 Correct 58 ms 43464 KB Output is correct
11 Correct 72 ms 45484 KB Output is correct
12 Correct 60 ms 42180 KB Output is correct
13 Correct 68 ms 39640 KB Output is correct
14 Correct 57 ms 43720 KB Output is correct
15 Correct 99 ms 43872 KB Output is correct
16 Correct 100 ms 47712 KB Output is correct
17 Correct 102 ms 42028 KB Output is correct
18 Correct 93 ms 41680 KB Output is correct
19 Incorrect 203 ms 54120 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 22876 KB Output is correct
2 Correct 5 ms 22876 KB Output is correct
3 Correct 6 ms 22876 KB Output is correct
4 Correct 6 ms 22876 KB Output is correct
5 Correct 5 ms 22876 KB Output is correct
6 Correct 5 ms 22872 KB Output is correct
7 Correct 5 ms 22876 KB Output is correct
8 Correct 5 ms 22960 KB Output is correct
9 Correct 5 ms 22876 KB Output is correct
10 Correct 53 ms 43716 KB Output is correct
11 Correct 58 ms 43464 KB Output is correct
12 Correct 72 ms 45484 KB Output is correct
13 Correct 60 ms 42180 KB Output is correct
14 Correct 68 ms 39640 KB Output is correct
15 Correct 57 ms 43720 KB Output is correct
16 Correct 99 ms 43872 KB Output is correct
17 Correct 100 ms 47712 KB Output is correct
18 Correct 102 ms 42028 KB Output is correct
19 Correct 93 ms 41680 KB Output is correct
20 Incorrect 203 ms 54120 KB Output isn't correct
21 Halted 0 ms 0 KB -