oj.uz

Submission #928396

# Submission time Handle Problem Language Result Execution time Memory
928396 2024-02-16T10:02:43 Z VinhLuu Swapping Cities (APIO20_swap) C++17
24 / 100
 2000 ms 87700 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);
        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 4 ms 27224 KB Output is correct
2 Correct 5 ms 27228 KB Output is correct
3 Correct 4 ms 27288 KB Output is correct
4 Correct 14 ms 27312 KB Output is correct
5 Correct 24 ms 27304 KB Output is correct
6 Correct 21 ms 27224 KB Output is correct
7 Correct 22 ms 27484 KB Output is correct
8 Correct 22 ms 27496 KB Output is correct
9 Correct 1459 ms 71420 KB Output is correct
10 Correct 1787 ms 83352 KB Output is correct
11 Correct 1746 ms 82092 KB Output is correct
12 Correct 1871 ms 86172 KB Output is correct
13 Correct 1822 ms 80620 KB Output is correct
14 Correct 1518 ms 73788 KB Output is correct
15 Execution timed out 2035 ms 87700 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.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 1866 ms 74548 KB Output is correct
4 Correct 1956 ms 76632 KB Output is correct
5 Correct 1919 ms 77000 KB Output is correct
6 Correct 1949 ms 76212 KB Output is correct
7 Correct 1979 ms 76764 KB Output is correct
8 Correct 1846 ms 74732 KB Output is correct
9 Correct 1960 ms 76504 KB Output is correct
10 Correct 1839 ms 74848 KB Output is correct

Subtask #3
17.0 / 17.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 27288 KB Output is correct
4 Correct 14 ms 27312 KB Output is correct
5 Correct 24 ms 27304 KB Output is correct
6 Correct 21 ms 27224 KB Output is correct
7 Correct 22 ms 27484 KB Output is correct
8 Correct 22 ms 27496 KB Output is correct
9 Correct 5 ms 27228 KB Output is correct
10 Correct 22 ms 27380 KB Output is correct
11 Correct 22 ms 27220 KB Output is correct
12 Correct 21 ms 27228 KB Output is correct
13 Correct 19 ms 27228 KB Output is correct
14 Correct 21 ms 27228 KB Output is correct
15 Correct 22 ms 27228 KB Output is correct
16 Correct 23 ms 27484 KB Output is correct
17 Correct 22 ms 27476 KB Output is correct
18 Correct 22 ms 27220 KB Output is correct
19 Correct 22 ms 27312 KB Output is correct
20 Correct 22 ms 27416 KB Output is correct
21 Correct 24 ms 27220 KB Output is correct
22 Correct 39 ms 27264 KB Output is correct
23 Correct 19 ms 27328 KB Output is correct
24 Correct 39 ms 27476 KB Output is correct
25 Correct 43 ms 27376 KB Output is correct
26 Correct 42 ms 27556 KB Output is correct
27 Correct 22 ms 27484 KB Output is correct
28 Correct 40 ms 27476 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 4 ms 27224 KB Output is correct
3 Correct 5 ms 27228 KB Output is correct
4 Correct 4 ms 27288 KB Output is correct
5 Correct 14 ms 27312 KB Output is correct
6 Correct 24 ms 27304 KB Output is correct
7 Correct 21 ms 27224 KB Output is correct
8 Correct 22 ms 27484 KB Output is correct
9 Correct 22 ms 27496 KB Output is correct
10 Correct 1459 ms 71420 KB Output is correct
11 Correct 1787 ms 83352 KB Output is correct
12 Correct 1746 ms 82092 KB Output is correct
13 Correct 1871 ms 86172 KB Output is correct
14 Correct 1822 ms 80620 KB Output is correct
15 Correct 22 ms 27380 KB Output is correct
16 Correct 22 ms 27220 KB Output is correct
17 Correct 21 ms 27228 KB Output is correct
18 Correct 19 ms 27228 KB Output is correct
19 Correct 21 ms 27228 KB Output is correct
20 Correct 22 ms 27228 KB Output is correct
21 Correct 23 ms 27484 KB Output is correct
22 Correct 22 ms 27476 KB Output is correct
23 Correct 22 ms 27220 KB Output is correct
24 Correct 22 ms 27312 KB Output is correct
25 Correct 22 ms 27416 KB Output is correct
26 Correct 24 ms 27220 KB Output is correct
27 Correct 39 ms 27264 KB Output is correct
28 Correct 19 ms 27328 KB Output is correct
29 Correct 39 ms 27476 KB Output is correct
30 Correct 43 ms 27376 KB Output is correct
31 Correct 42 ms 27556 KB Output is correct
32 Correct 22 ms 27484 KB Output is correct
33 Correct 40 ms 27476 KB Output is correct
34 Correct 273 ms 31608 KB Output is correct
35 Correct 1883 ms 81588 KB Output is correct
36 Correct 1887 ms 78740 KB Output is correct
37 Correct 1860 ms 76084 KB Output is correct
38 Correct 1808 ms 74924 KB Output is correct
39 Correct 1817 ms 74480 KB Output is correct
40 Correct 1657 ms 68044 KB Output is correct
41 Correct 1871 ms 81512 KB Output is correct
42 Correct 1854 ms 81508 KB Output is correct
43 Correct 1833 ms 86492 KB Output is correct
44 Correct 1857 ms 76808 KB Output is correct
45 Execution timed out 2063 ms 33616 KB Time limit exceeded
46 Halted 0 ms 0 KB -

Subtask #5
0 / 23.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 27288 KB Output is correct
4 Correct 14 ms 27312 KB Output is correct
5 Correct 24 ms 27304 KB Output is correct
6 Correct 21 ms 27224 KB Output is correct
7 Correct 22 ms 27484 KB Output is correct
8 Correct 22 ms 27496 KB Output is correct
9 Correct 1459 ms 71420 KB Output is correct
10 Correct 1787 ms 83352 KB Output is correct
11 Correct 1746 ms 82092 KB Output is correct
12 Correct 1871 ms 86172 KB Output is correct
13 Correct 1822 ms 80620 KB Output is correct
14 Correct 1518 ms 73788 KB Output is correct
15 Execution timed out 2035 ms 87700 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 4 ms 27224 KB Output is correct
3 Correct 5 ms 27228 KB Output is correct
4 Correct 4 ms 27288 KB Output is correct
5 Correct 14 ms 27312 KB Output is correct
6 Correct 24 ms 27304 KB Output is correct
7 Correct 21 ms 27224 KB Output is correct
8 Correct 22 ms 27484 KB Output is correct
9 Correct 22 ms 27496 KB Output is correct
10 Correct 1459 ms 71420 KB Output is correct
11 Correct 1787 ms 83352 KB Output is correct
12 Correct 1746 ms 82092 KB Output is correct
13 Correct 1871 ms 86172 KB Output is correct
14 Correct 1822 ms 80620 KB Output is correct
15 Correct 1518 ms 73788 KB Output is correct
16 Execution timed out 2035 ms 87700 KB Time limit exceeded
17 Halted 0 ms 0 KB -