oj.uz

Submission #928363

# Submission time Handle Problem Language Result Execution time Memory
928363 2024-02-16T09:03:58 Z VinhLuu Swapping Cities (APIO20_swap) C++17
13 / 100
 427 ms 82088 KB 
#include <bits/stdc++.h>
//#define int long long
//#define ll long long
#define fi first
#define se second
#define pb push_back
using namespace std;

typedef pair<int,int> pii;
typedef tuple<int,int,int> tp;
const int N = 2e5 + 5;
const int oo = 2e9;
//const int mod = 1e9 + 7;

struct e{
    int u, v, w;
} p[N];

bool comp(e g1, e g2){
    return g1.w < g2.w;
}

int n, m, d[N], in[2][N], out[2][N], dp[2][N][22], mx[2][N][22], demin[2], demout[2], root, pa[N], sz[N], f[N], deg[N];
vector<pii> g[2][N];

int fin(int u){
    return pa[u] == u ? u : fin(pa[u]);
}

void dfs(int t,int u,int v,int ts){
    in[t][u] = ++demin[t];
    if(u == root) for(int i = 0; i <= 20; i ++) dp[t][u][i] = u;
    else{
        dp[t][u][0] = v;
        mx[t][u][0] = ts;
        for(int i = 1; i <= 20; i ++){
            dp[t][u][i] = dp[t][dp[t][u][i - 1]][i - 1];
            mx[t][u][i] = max(mx[t][u][i - 1], mx[t][dp[t][u][i - 1]][i - 1]);
        }
    }
    for(auto jj : g[t][u]){
        int j = jj.fi;
        int w = jj.se;
        if(j == v) continue;
        if(t == 0) f[j] = min(f[j], max(f[u], w));
        dfs(t, j, u, w);
    }
    out[t][u] = ++demout[t];
}

bool kt(int t,int u,int v){
    return in[t][u] <= in[t][v] && out[t][u] >= out[t][v];
}

int lca(int t,int u,int v){
    if(kt(t, u, v)) return u;
    else{
        int kq = u;
        for(int i = 20; i >= 0; i --){
            if(kt(t, dp[t][u][i], v)) kq = dp[t][u][i];
            else u = dp[t][u][i];
        }
        return kq;
    }
}

int get(int u,int v){
    int ret = 0, k = lca(1, u, v), tmp = u;
    for(int i = 20; i >= 0; i --){
        if(!kt(1, dp[1][u][i], v) || dp[1][u][i] == k){
            ret = max(ret, mx[1][u][i]);
            u = dp[1][u][i];
        }
    }
    u = tmp;
    for(int i = 20; i >= 0; i --){
        if(!kt(1, dp[1][v][i], u) || dp[1][v][i] == k){
            ret = max(ret, mx[1][v][i]);
            v = dp[1][v][i];
        }
    }
    return ret;
}

void dsu(int x,int y,int w){
    int u = x, v = y;
    x = fin(x);
    y = fin(y);
    if(x == y){
        f[x] = min(f[x], w);
        return;
    }
    if(sz[x] < sz[y]) swap(x, y);
    sz[x] += sz[y];
    pa[y] = x;
//    cerr << x << " " << y << " " << w << " f\n";
    g[0][x].push_back({y, w});
    g[1][u].pb({v, w});
    g[1][v].pb({u, w});
    f[x] = min(f[x], f[y]);
    d[x] = max(d[x], d[y]);
//    re[x] = max({re[x], re[y], w});
}

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

    for(int i = 0; i < m; i ++){
        p[i + 1].u = U[i] + 1;
        p[i + 1].v = V[i] + 1;
        p[i + 1].w = W[i];
    }
    sort(p + 1, p + m + 1, comp);
    for(int i = 1; i <= m; i ++){
        if(p[i].u == p[i].v) continue;
        dsu(p[i].u, p[i].v, p[i].w);
        int u = p[i].u, v = p[i].v, w = p[i].w;
        deg[u]++;
        deg[v]++;

        int j = fin(u);
        d[j] = max({d[j], deg[u], deg[v]});
        if(d[j] >= 3) f[j] = min(f[j], w);
//        cerr << u << " " << v << " " << w << " " << j << " " << f[j] << " gggg\n";
    }

    root = fin(1);
//    cerr << root << " g\n";
    dfs(0, root, 0, 0);
    dfs(1, root, 0, 0);
}

int getMinimumFuelCapacity(int x,int y){
    x++;
    y++;

    int t = lca(0, x, y), kq = max(f[t], get(x, y));
//    cerr << x << " " << y << " " << t << " " << f[t] << " " << get(x, y) << "f\n";
    if(f[t] == (int)oo) return -1;
    return kq;
}

//#define LOCAL

#ifdef LOCAL
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    #define task "v"
    if(fopen(task ".inp","r")){
        freopen(task ".inp","r",stdin);
        freopen(task ".out","w",stdout);
    }

    cin >> n >> m;
    vector<int> u, v, w;
    for(int i = 1; i <= m; i ++){
        int x, y, t; cin >> x >> y >> t;
        u.pb(x - 1);
        v.pb(y - 1);
        w.pb(t);
    }
    init(n, m, u, v, w);
    int rq = 0;
    cin >> rq;
//    cerr << rq << "fifai\n";
    while(rq--){
        int x, y;
        cin >> x >> y;
//        cerr << x << " " << y << " rr\n";
        x--;
        y--;

        cout << getMinimumFuelCapacity(x, y) << "\n";
    }
}
#endif // LOCAL

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 27228 KB Output is correct
2 Correct 4 ms 27228 KB Output is correct
3 Correct 4 ms 27228 KB Output is correct
4 Correct 4 ms 27556 KB Output is correct
5 Correct 5 ms 27236 KB Output is correct
6 Correct 5 ms 27228 KB Output is correct
7 Correct 5 ms 27228 KB Output is correct
8 Correct 5 ms 27224 KB Output is correct
9 Correct 110 ms 65160 KB Output is correct
10 Correct 129 ms 75552 KB Output is correct
11 Correct 121 ms 74320 KB Output is correct
12 Correct 164 ms 77976 KB Output is correct
13 Correct 115 ms 72716 KB Output is correct
14 Correct 123 ms 67360 KB Output is correct
15 Correct 382 ms 78912 KB Output is correct
16 Correct 384 ms 73416 KB Output is correct
17 Correct 427 ms 77748 KB Output is correct
18 Correct 354 ms 79744 KB Output is correct
19 Correct 156 ms 37032 KB Output is correct
20 Correct 368 ms 80252 KB Output is correct
21 Correct 377 ms 73920 KB Output is correct
22 Correct 415 ms 77976 KB Output is correct
23 Correct 374 ms 82088 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 27228 KB Output is correct
2 Correct 4 ms 27228 KB Output is correct
3 Correct 262 ms 67804 KB Output is correct
4 Correct 258 ms 69076 KB Output is correct
5 Correct 308 ms 70012 KB Output is correct
6 Correct 260 ms 69096 KB Output is correct
7 Correct 267 ms 69204 KB Output is correct
8 Correct 278 ms 67908 KB Output is correct
9 Correct 259 ms 69168 KB Output is correct
10 Correct 306 ms 67616 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 27228 KB Output is correct
2 Correct 4 ms 27228 KB Output is correct
3 Correct 4 ms 27228 KB Output is correct
4 Correct 4 ms 27556 KB Output is correct
5 Correct 5 ms 27236 KB Output is correct
6 Correct 5 ms 27228 KB Output is correct
7 Correct 5 ms 27228 KB Output is correct
8 Correct 5 ms 27224 KB Output is correct
9 Correct 4 ms 27228 KB Output is correct
10 Correct 5 ms 27228 KB Output is correct
11 Correct 5 ms 27228 KB Output is correct
12 Correct 5 ms 27228 KB Output is correct
13 Correct 5 ms 27228 KB Output is correct
14 Correct 5 ms 27228 KB Output is correct
15 Correct 5 ms 27228 KB Output is correct
16 Correct 5 ms 27284 KB Output is correct
17 Correct 6 ms 27484 KB Output is correct
18 Correct 5 ms 27292 KB Output is correct
19 Correct 5 ms 27480 KB Output is correct
20 Correct 5 ms 27228 KB Output is correct
21 Correct 5 ms 27224 KB Output is correct
22 Correct 5 ms 27352 KB Output is correct
23 Correct 5 ms 27236 KB Output is correct
24 Incorrect 6 ms 27228 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 27228 KB Output is correct
2 Correct 5 ms 27228 KB Output is correct
3 Correct 4 ms 27228 KB Output is correct
4 Correct 4 ms 27228 KB Output is correct
5 Correct 4 ms 27556 KB Output is correct
6 Correct 5 ms 27236 KB Output is correct
7 Correct 5 ms 27228 KB Output is correct
8 Correct 5 ms 27228 KB Output is correct
9 Correct 5 ms 27224 KB Output is correct
10 Correct 110 ms 65160 KB Output is correct
11 Correct 129 ms 75552 KB Output is correct
12 Correct 121 ms 74320 KB Output is correct
13 Correct 164 ms 77976 KB Output is correct
14 Correct 115 ms 72716 KB Output is correct
15 Correct 5 ms 27228 KB Output is correct
16 Correct 5 ms 27228 KB Output is correct
17 Correct 5 ms 27228 KB Output is correct
18 Correct 5 ms 27228 KB Output is correct
19 Correct 5 ms 27228 KB Output is correct
20 Correct 5 ms 27228 KB Output is correct
21 Correct 5 ms 27284 KB Output is correct
22 Correct 6 ms 27484 KB Output is correct
23 Correct 5 ms 27292 KB Output is correct
24 Correct 5 ms 27480 KB Output is correct
25 Correct 5 ms 27228 KB Output is correct
26 Correct 5 ms 27224 KB Output is correct
27 Correct 5 ms 27352 KB Output is correct
28 Correct 5 ms 27236 KB Output is correct
29 Incorrect 6 ms 27228 KB Output isn't correct
30 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 27228 KB Output is correct
2 Correct 4 ms 27228 KB Output is correct
3 Correct 4 ms 27228 KB Output is correct
4 Correct 4 ms 27556 KB Output is correct
5 Correct 5 ms 27236 KB Output is correct
6 Correct 5 ms 27228 KB Output is correct
7 Correct 5 ms 27228 KB Output is correct
8 Correct 5 ms 27224 KB Output is correct
9 Correct 110 ms 65160 KB Output is correct
10 Correct 129 ms 75552 KB Output is correct
11 Correct 121 ms 74320 KB Output is correct
12 Correct 164 ms 77976 KB Output is correct
13 Correct 115 ms 72716 KB Output is correct
14 Correct 123 ms 67360 KB Output is correct
15 Correct 382 ms 78912 KB Output is correct
16 Correct 384 ms 73416 KB Output is correct
17 Correct 427 ms 77748 KB Output is correct
18 Correct 354 ms 79744 KB Output is correct
19 Correct 262 ms 67804 KB Output is correct
20 Correct 258 ms 69076 KB Output is correct
21 Correct 308 ms 70012 KB Output is correct
22 Correct 260 ms 69096 KB Output is correct
23 Correct 267 ms 69204 KB Output is correct
24 Correct 278 ms 67908 KB Output is correct
25 Correct 259 ms 69168 KB Output is correct
26 Correct 306 ms 67616 KB Output is correct
27 Correct 5 ms 27228 KB Output is correct
28 Correct 5 ms 27228 KB Output is correct
29 Correct 5 ms 27228 KB Output is correct
30 Correct 5 ms 27228 KB Output is correct
31 Correct 5 ms 27228 KB Output is correct
32 Correct 5 ms 27228 KB Output is correct
33 Correct 5 ms 27284 KB Output is correct
34 Correct 6 ms 27484 KB Output is correct
35 Correct 5 ms 27292 KB Output is correct
36 Correct 14 ms 30300 KB Output is correct
37 Correct 140 ms 73812 KB Output is correct
38 Correct 126 ms 71248 KB Output is correct
39 Correct 138 ms 68132 KB Output is correct
40 Correct 110 ms 67672 KB Output is correct
41 Correct 113 ms 67348 KB Output is correct
42 Correct 108 ms 61812 KB Output is correct
43 Incorrect 159 ms 73516 KB Output isn't correct
44 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 27228 KB Output is correct
2 Correct 5 ms 27228 KB Output is correct
3 Correct 4 ms 27228 KB Output is correct
4 Correct 4 ms 27228 KB Output is correct
5 Correct 4 ms 27556 KB Output is correct
6 Correct 5 ms 27236 KB Output is correct
7 Correct 5 ms 27228 KB Output is correct
8 Correct 5 ms 27228 KB Output is correct
9 Correct 5 ms 27224 KB Output is correct
10 Correct 110 ms 65160 KB Output is correct
11 Correct 129 ms 75552 KB Output is correct
12 Correct 121 ms 74320 KB Output is correct
13 Correct 164 ms 77976 KB Output is correct
14 Correct 115 ms 72716 KB Output is correct
15 Correct 123 ms 67360 KB Output is correct
16 Correct 382 ms 78912 KB Output is correct
17 Correct 384 ms 73416 KB Output is correct
18 Correct 427 ms 77748 KB Output is correct
19 Correct 354 ms 79744 KB Output is correct
20 Correct 262 ms 67804 KB Output is correct
21 Correct 258 ms 69076 KB Output is correct
22 Correct 308 ms 70012 KB Output is correct
23 Correct 260 ms 69096 KB Output is correct
24 Correct 267 ms 69204 KB Output is correct
25 Correct 278 ms 67908 KB Output is correct
26 Correct 259 ms 69168 KB Output is correct
27 Correct 306 ms 67616 KB Output is correct
28 Correct 5 ms 27228 KB Output is correct
29 Correct 5 ms 27228 KB Output is correct
30 Correct 5 ms 27228 KB Output is correct
31 Correct 5 ms 27228 KB Output is correct
32 Correct 5 ms 27228 KB Output is correct
33 Correct 5 ms 27228 KB Output is correct
34 Correct 5 ms 27284 KB Output is correct
35 Correct 6 ms 27484 KB Output is correct
36 Correct 5 ms 27292 KB Output is correct
37 Correct 14 ms 30300 KB Output is correct
38 Correct 140 ms 73812 KB Output is correct
39 Correct 126 ms 71248 KB Output is correct
40 Correct 138 ms 68132 KB Output is correct
41 Correct 110 ms 67672 KB Output is correct
42 Correct 113 ms 67348 KB Output is correct
43 Correct 108 ms 61812 KB Output is correct
44 Incorrect 159 ms 73516 KB Output isn't correct
45 Halted 0 ms 0 KB -