oj.uz

Submission #928397

# Submission time Handle Problem Language Result Execution time Memory
928397 2024-02-16T10:04:37 Z VinhLuu Swapping Cities (APIO20_swap) C++17
17 / 100
 2000 ms 85176 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 <= 17; i ++) dp[t][u][i] = u;
    else{
        dp[t][u][0] = v;
        mx[t][u][0] = ts;
        for(int i = 1; i <= 17; 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 = 17; 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 = 17; 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 = 17; 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);
        cerr << u << " " << v << " " << x << " " << f[x] << "change\n";
        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], max(w, 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
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 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 12 ms 27228 KB Output is correct
5 Correct 21 ms 27228 KB Output is correct
6 Correct 22 ms 27228 KB Output is correct
7 Correct 24 ms 27484 KB Output is correct
8 Correct 22 ms 27220 KB Output is correct
9 Correct 1459 ms 70360 KB Output is correct
10 Correct 1768 ms 82508 KB Output is correct
11 Correct 1743 ms 80820 KB Output is correct
12 Correct 1855 ms 84680 KB Output is correct
13 Correct 1824 ms 79568 KB Output is correct
14 Correct 1469 ms 72572 KB Output is correct
15 Execution timed out 2041 ms 85176 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 27228 KB Output is correct
2 Correct 4 ms 27228 KB Output is correct
3 Correct 1855 ms 72716 KB Output is correct
4 Correct 1955 ms 74276 KB Output is correct
5 Correct 1891 ms 74880 KB Output is correct
6 Execution timed out 2031 ms 74012 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 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 12 ms 27228 KB Output is correct
5 Correct 21 ms 27228 KB Output is correct
6 Correct 22 ms 27228 KB Output is correct
7 Correct 24 ms 27484 KB Output is correct
8 Correct 22 ms 27220 KB Output is correct
9 Correct 5 ms 27228 KB Output is correct
10 Correct 23 ms 27352 KB Output is correct
11 Correct 22 ms 27228 KB Output is correct
12 Correct 23 ms 27560 KB Output is correct
13 Correct 19 ms 27228 KB Output is correct
14 Correct 19 ms 27320 KB Output is correct
15 Correct 22 ms 27228 KB Output is correct
16 Correct 27 ms 27224 KB Output is correct
17 Correct 21 ms 27484 KB Output is correct
18 Correct 22 ms 27304 KB Output is correct
19 Correct 22 ms 27360 KB Output is correct
20 Correct 22 ms 27384 KB Output is correct
21 Correct 24 ms 27336 KB Output is correct
22 Correct 38 ms 27572 KB Output is correct
23 Correct 19 ms 27228 KB Output is correct
24 Correct 40 ms 27644 KB Output is correct
25 Correct 38 ms 27352 KB Output is correct
26 Correct 41 ms 27472 KB Output is correct
27 Correct 22 ms 27484 KB Output is correct
28 Correct 39 ms 27404 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 27228 KB Output is correct
2 Correct 7 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 12 ms 27228 KB Output is correct
6 Correct 21 ms 27228 KB Output is correct
7 Correct 22 ms 27228 KB Output is correct
8 Correct 24 ms 27484 KB Output is correct
9 Correct 22 ms 27220 KB Output is correct
10 Correct 1459 ms 70360 KB Output is correct
11 Correct 1768 ms 82508 KB Output is correct
12 Correct 1743 ms 80820 KB Output is correct
13 Correct 1855 ms 84680 KB Output is correct
14 Correct 1824 ms 79568 KB Output is correct
15 Correct 23 ms 27352 KB Output is correct
16 Correct 22 ms 27228 KB Output is correct
17 Correct 23 ms 27560 KB Output is correct
18 Correct 19 ms 27228 KB Output is correct
19 Correct 19 ms 27320 KB Output is correct
20 Correct 22 ms 27228 KB Output is correct
21 Correct 27 ms 27224 KB Output is correct
22 Correct 21 ms 27484 KB Output is correct
23 Correct 22 ms 27304 KB Output is correct
24 Correct 22 ms 27360 KB Output is correct
25 Correct 22 ms 27384 KB Output is correct
26 Correct 24 ms 27336 KB Output is correct
27 Correct 38 ms 27572 KB Output is correct
28 Correct 19 ms 27228 KB Output is correct
29 Correct 40 ms 27644 KB Output is correct
30 Correct 38 ms 27352 KB Output is correct
31 Correct 41 ms 27472 KB Output is correct
32 Correct 22 ms 27484 KB Output is correct
33 Correct 39 ms 27404 KB Output is correct
34 Correct 250 ms 31128 KB Output is correct
35 Correct 1860 ms 80260 KB Output is correct
36 Correct 1857 ms 77608 KB Output is correct
37 Correct 1831 ms 74112 KB Output is correct
38 Correct 1809 ms 73808 KB Output is correct
39 Correct 1806 ms 73352 KB Output is correct
40 Correct 1627 ms 67264 KB Output is correct
41 Correct 1874 ms 80264 KB Output is correct
42 Correct 1850 ms 79664 KB Output is correct
43 Correct 1813 ms 84508 KB Output is correct
44 Correct 1847 ms 74760 KB Output is correct
45 Execution timed out 2040 ms 30440 KB Time limit exceeded
46 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 7 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 12 ms 27228 KB Output is correct
5 Correct 21 ms 27228 KB Output is correct
6 Correct 22 ms 27228 KB Output is correct
7 Correct 24 ms 27484 KB Output is correct
8 Correct 22 ms 27220 KB Output is correct
9 Correct 1459 ms 70360 KB Output is correct
10 Correct 1768 ms 82508 KB Output is correct
11 Correct 1743 ms 80820 KB Output is correct
12 Correct 1855 ms 84680 KB Output is correct
13 Correct 1824 ms 79568 KB Output is correct
14 Correct 1469 ms 72572 KB Output is correct
15 Execution timed out 2041 ms 85176 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 27228 KB Output is correct
2 Correct 7 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 12 ms 27228 KB Output is correct
6 Correct 21 ms 27228 KB Output is correct
7 Correct 22 ms 27228 KB Output is correct
8 Correct 24 ms 27484 KB Output is correct
9 Correct 22 ms 27220 KB Output is correct
10 Correct 1459 ms 70360 KB Output is correct
11 Correct 1768 ms 82508 KB Output is correct
12 Correct 1743 ms 80820 KB Output is correct
13 Correct 1855 ms 84680 KB Output is correct
14 Correct 1824 ms 79568 KB Output is correct
15 Correct 1469 ms 72572 KB Output is correct
16 Execution timed out 2041 ms 85176 KB Time limit exceeded
17 Halted 0 ms 0 KB -