oj.uz

Submission #928362

# Submission time Handle Problem Language Result Execution time Memory
928362 2024-02-16T09:01:53 Z VinhLuu Swapping Cities (APIO20_swap) C++17
13 / 100
 428 ms 86440 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] = 1e9;
        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)1e9) 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 5 ms 27292 KB Output is correct
4 Correct 5 ms 27228 KB Output is correct
5 Correct 5 ms 27228 KB Output is correct
6 Correct 5 ms 27352 KB Output is correct
7 Correct 5 ms 27224 KB Output is correct
8 Correct 5 ms 27224 KB Output is correct
9 Correct 102 ms 66816 KB Output is correct
10 Correct 141 ms 77640 KB Output is correct
11 Correct 141 ms 76316 KB Output is correct
12 Correct 135 ms 79992 KB Output is correct
13 Correct 115 ms 74720 KB Output is correct
14 Correct 122 ms 69000 KB Output is correct
15 Correct 383 ms 83296 KB Output is correct
16 Correct 393 ms 77560 KB Output is correct
17 Correct 413 ms 82100 KB Output is correct
18 Correct 363 ms 84392 KB Output is correct
19 Correct 146 ms 39044 KB Output is correct
20 Correct 358 ms 84440 KB Output is correct
21 Correct 428 ms 78240 KB Output is correct
22 Correct 382 ms 82216 KB Output is correct
23 Correct 372 ms 86440 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 252 ms 67804 KB Output is correct
4 Correct 264 ms 69284 KB Output is correct
5 Correct 274 ms 70008 KB Output is correct
6 Correct 269 ms 69468 KB Output is correct
7 Correct 293 ms 69520 KB Output is correct
8 Correct 265 ms 67704 KB Output is correct
9 Correct 255 ms 69208 KB Output is correct
10 Correct 270 ms 67664 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 5 ms 27292 KB Output is correct
4 Correct 5 ms 27228 KB Output is correct
5 Correct 5 ms 27228 KB Output is correct
6 Correct 5 ms 27352 KB Output is correct
7 Correct 5 ms 27224 KB Output is correct
8 Correct 5 ms 27224 KB Output is correct
9 Correct 4 ms 27224 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 6 ms 27236 KB Output is correct
14 Correct 5 ms 27228 KB Output is correct
15 Correct 6 ms 27276 KB Output is correct
16 Correct 5 ms 27216 KB Output is correct
17 Correct 5 ms 27484 KB Output is correct
18 Correct 5 ms 27228 KB Output is correct
19 Correct 6 ms 27364 KB Output is correct
20 Correct 5 ms 27732 KB Output is correct
21 Correct 5 ms 27228 KB Output is correct
22 Correct 5 ms 27328 KB Output is correct
23 Correct 5 ms 27224 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 27224 KB Output is correct
2 Correct 5 ms 27228 KB Output is correct
3 Correct 4 ms 27228 KB Output is correct
4 Correct 5 ms 27292 KB Output is correct
5 Correct 5 ms 27228 KB Output is correct
6 Correct 5 ms 27228 KB Output is correct
7 Correct 5 ms 27352 KB Output is correct
8 Correct 5 ms 27224 KB Output is correct
9 Correct 5 ms 27224 KB Output is correct
10 Correct 102 ms 66816 KB Output is correct
11 Correct 141 ms 77640 KB Output is correct
12 Correct 141 ms 76316 KB Output is correct
13 Correct 135 ms 79992 KB Output is correct
14 Correct 115 ms 74720 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 6 ms 27236 KB Output is correct
19 Correct 5 ms 27228 KB Output is correct
20 Correct 6 ms 27276 KB Output is correct
21 Correct 5 ms 27216 KB Output is correct
22 Correct 5 ms 27484 KB Output is correct
23 Correct 5 ms 27228 KB Output is correct
24 Correct 6 ms 27364 KB Output is correct
25 Correct 5 ms 27732 KB Output is correct
26 Correct 5 ms 27228 KB Output is correct
27 Correct 5 ms 27328 KB Output is correct
28 Correct 5 ms 27224 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 5 ms 27292 KB Output is correct
4 Correct 5 ms 27228 KB Output is correct
5 Correct 5 ms 27228 KB Output is correct
6 Correct 5 ms 27352 KB Output is correct
7 Correct 5 ms 27224 KB Output is correct
8 Correct 5 ms 27224 KB Output is correct
9 Correct 102 ms 66816 KB Output is correct
10 Correct 141 ms 77640 KB Output is correct
11 Correct 141 ms 76316 KB Output is correct
12 Correct 135 ms 79992 KB Output is correct
13 Correct 115 ms 74720 KB Output is correct
14 Correct 122 ms 69000 KB Output is correct
15 Correct 383 ms 83296 KB Output is correct
16 Correct 393 ms 77560 KB Output is correct
17 Correct 413 ms 82100 KB Output is correct
18 Correct 363 ms 84392 KB Output is correct
19 Correct 252 ms 67804 KB Output is correct
20 Correct 264 ms 69284 KB Output is correct
21 Correct 274 ms 70008 KB Output is correct
22 Correct 269 ms 69468 KB Output is correct
23 Correct 293 ms 69520 KB Output is correct
24 Correct 265 ms 67704 KB Output is correct
25 Correct 255 ms 69208 KB Output is correct
26 Correct 270 ms 67664 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 6 ms 27236 KB Output is correct
31 Correct 5 ms 27228 KB Output is correct
32 Correct 6 ms 27276 KB Output is correct
33 Correct 5 ms 27216 KB Output is correct
34 Correct 5 ms 27484 KB Output is correct
35 Correct 5 ms 27228 KB Output is correct
36 Correct 15 ms 30628 KB Output is correct
37 Correct 155 ms 75604 KB Output is correct
38 Correct 133 ms 73092 KB Output is correct
39 Correct 124 ms 69824 KB Output is correct
40 Correct 126 ms 69668 KB Output is correct
41 Correct 115 ms 69200 KB Output is correct
42 Correct 97 ms 63444 KB Output is correct
43 Incorrect 156 ms 75648 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 27224 KB Output is correct
2 Correct 5 ms 27228 KB Output is correct
3 Correct 4 ms 27228 KB Output is correct
4 Correct 5 ms 27292 KB Output is correct
5 Correct 5 ms 27228 KB Output is correct
6 Correct 5 ms 27228 KB Output is correct
7 Correct 5 ms 27352 KB Output is correct
8 Correct 5 ms 27224 KB Output is correct
9 Correct 5 ms 27224 KB Output is correct
10 Correct 102 ms 66816 KB Output is correct
11 Correct 141 ms 77640 KB Output is correct
12 Correct 141 ms 76316 KB Output is correct
13 Correct 135 ms 79992 KB Output is correct
14 Correct 115 ms 74720 KB Output is correct
15 Correct 122 ms 69000 KB Output is correct
16 Correct 383 ms 83296 KB Output is correct
17 Correct 393 ms 77560 KB Output is correct
18 Correct 413 ms 82100 KB Output is correct
19 Correct 363 ms 84392 KB Output is correct
20 Correct 252 ms 67804 KB Output is correct
21 Correct 264 ms 69284 KB Output is correct
22 Correct 274 ms 70008 KB Output is correct
23 Correct 269 ms 69468 KB Output is correct
24 Correct 293 ms 69520 KB Output is correct
25 Correct 265 ms 67704 KB Output is correct
26 Correct 255 ms 69208 KB Output is correct
27 Correct 270 ms 67664 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 6 ms 27236 KB Output is correct
32 Correct 5 ms 27228 KB Output is correct
33 Correct 6 ms 27276 KB Output is correct
34 Correct 5 ms 27216 KB Output is correct
35 Correct 5 ms 27484 KB Output is correct
36 Correct 5 ms 27228 KB Output is correct
37 Correct 15 ms 30628 KB Output is correct
38 Correct 155 ms 75604 KB Output is correct
39 Correct 133 ms 73092 KB Output is correct
40 Correct 124 ms 69824 KB Output is correct
41 Correct 126 ms 69668 KB Output is correct
42 Correct 115 ms 69200 KB Output is correct
43 Correct 97 ms 63444 KB Output is correct
44 Incorrect 156 ms 75648 KB Output isn't correct
45 Halted 0 ms 0 KB -