oj.uz

Submission #1109715

# Submission time Handle Problem Language Result Execution time Memory
1109715 2024-11-07T11:05:32 Z Mike_Vu Swapping Cities (APIO20_swap) C++14
13 / 100
 258 ms 61756 KB 
#ifndef mikevui
//    #include "task.h"
#endif // mikevui

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double dou;
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
#define MASK(x) (1LL<<(x))
#define BITj(x, j) (((x)>>(j))&1)

template<typename T> bool maximize(T &x, const T &y) {
    if (x < y) {x = y; return 1;}
    return 0;
}
template<typename T> bool minimize(T &x, const T &y) {
    if (x > y) {x = y; return 1;}
    return 0;
}

struct edge{
    int u, v, w;
    edge(int _u, int _v, int _w) {
        u = _u;
        v = _v;
        w = _w;
    }
};

const int maxn = 3e5+5, lg = 19;
int n, m, trsz;
vector<edge> edges;
bool can[maxn];
int ans[maxn];
vector<int> adj[maxn];
int par[maxn][lg+1], h[maxn];
bool hadcan[maxn][lg+1];

namespace dsu{
    vector<int> dsu, deg, sumdeg;
    void init() {
        trsz = n;
        memset(can, 0, sizeof(can));
        dsu.assign(trsz+1, 0);
        deg.assign(trsz+1, 0);
        sumdeg.assign(trsz+1, 1);
        for (int i = 1; i <= n; i++) {
            dsu[i] = i;
        }
    }
    int f(int u) {
        if (u == dsu[u]) return u;
        return dsu[u] = f(dsu[u]);
    }
    void addedge(int u, int v) {
        int ru = f(u), rv = f(v);
        ++trsz;
        dsu.pb(trsz);
        dsu[ru] = dsu[rv] = trsz;
        adj[trsz].pb(ru);
        if (ru != rv) adj[trsz].pb(rv);
        ++deg[u];
        ++deg[v];
        //check cycle
        sumdeg.pb(sumdeg[ru]);
        if (ru != rv) sumdeg[trsz] += sumdeg[rv];
        if (deg[u] == 2)--sumdeg[trsz];
        if (deg[v] == 2)--sumdeg[trsz];
//        cout << u << ' ' << v << ' ' << trsz << "\n" << deg[u] << ' ' << deg[v] << ' ' << sumdeg[ru] << ' ' << sumdeg[rv] << ' ' << sumdeg[trsz] << "\n";
        can[trsz] = (max(deg[u], deg[v])>2 || sumdeg[trsz] == 0);
    }
}

void dfs(int u) {
    //setup binlift
    for (int j = 1; j <= lg; j++) {
        par[u][j] = par[par[u][j-1]][j-1];
        hadcan[u][j] = hadcan[u][j-1]|hadcan[par[u][j-1]][j-1];
    }
    //dfs
    for (int v : adj[u]) {
        par[v][0] = u;
        hadcan[v][0] = can[u];
        h[v] = h[u]+1;
        dfs(v);
    }
}

int lca(int u, int v) {
    if (h[u] < h[v]) swap(u, v);
    if (h[u] > h[v]) {
        int k = h[u]-h[v];
        for (int j = lg; j >= 0; j--) {
            if (BITj(k, j)) {
                u = par[u][j];
            }
        }
    }
    if (u == v) return u;
    for (int j = lg; j >= 0; j--) {
        while (h[u] > MASK(j) && par[u][j] != par[v][j]) {
            u = par[u][j];
            v = par[v][j];
        }
    }
    return par[u][0];
}

int findnearest(int u){
    for (int j = lg; j >= 0; j--) {
        while (h[u] > MASK(j) && !hadcan[u][j]) {
            u = par[u][j];
        }
    }
    return par[u][0];
}

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
    //transform to normal use
    n = N;
    m = M;
    for (int i = 0; i < m; i++) {
        int u = U[i]+1, v = V[i]+1, w = W[i];
        edges.pb(edge(u, v, w));
    }
    //build dsu tree
    sort(edges.begin(), edges.end(), [&](edge a, edge b){return a.w<b.w;});
    dsu::init();
    for (int i= 0; i < m; i++) {
        dsu::addedge(edges[i].u, edges[i].v);
        ans[trsz] = edges[i].w;
    }
    //build binlift
    memset(par, 0, sizeof(par));
    memset(hadcan, 0, sizeof(hadcan));
    h[trsz] = 1;
    dfs(trsz);
//    for (int i = 1; i <= trsz; i++) {
//        cout << i << ' ' << h[i] << ' ' << can[i] << ' ' << ans[i] << "\n";
//    }
}

int getMinimumFuelCapacity(int X, int Y) {
    int x = X+1, y = Y+1;
    //lca
    int l = lca(x, y);
    //check if lca can
    if (can[l]) {
        return ans[l];
    }
    //if not -> find nearest can
    l = findnearest(l);
    //case cannot
    if (!can[l]) return -1;
    return ans[l];
}

#ifdef mikevui
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
//    #define name "task"
//    if (fopen(name".inp", "r")) {
//        freopen(name".inp", "r", stdin);
//        freopen(name".out", "w", stdout);
//    }
    int N, M;
    cin >> N >> M;
    vector<int> U, V, W;
    for (int i = 0; i < M; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        U.pb(u);
        V.pb(v);
        W.pb(w);
    }
    init(N,M,U,V,W);
    int Q;
    cin >> Q;
    while (Q--) {
        int X, Y;
        cin >> X >> Y;
        cout << getMinimumFuelCapacity(X,Y) << "\n";
    }
}
#endif // mikevui
/*
5 6
0 1 4
0 2 4
1 2 1
1 3 2
1 4 10
2 3 3
3
1 2
2 4
0 1

3 2
0 1 5
0 2 5
1
1 2
*/

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 38224 KB Output is correct
2 Correct 8 ms 38236 KB Output is correct
3 Correct 7 ms 38224 KB Output is correct
4 Correct 7 ms 38224 KB Output is correct
5 Correct 7 ms 38324 KB Output is correct
6 Correct 8 ms 38224 KB Output is correct
7 Correct 9 ms 38224 KB Output is correct
8 Correct 8 ms 38348 KB Output is correct
9 Correct 93 ms 45252 KB Output is correct
10 Correct 108 ms 46788 KB Output is correct
11 Correct 109 ms 48060 KB Output is correct
12 Correct 110 ms 48572 KB Output is correct
13 Correct 116 ms 51132 KB Output is correct
14 Correct 106 ms 47292 KB Output is correct
15 Correct 197 ms 53148 KB Output is correct
16 Correct 188 ms 52844 KB Output is correct
17 Correct 232 ms 53376 KB Output is correct
18 Correct 258 ms 57380 KB Output is correct
19 Correct 75 ms 45064 KB Output is correct
20 Correct 178 ms 54176 KB Output is correct
21 Correct 154 ms 54028 KB Output is correct
22 Correct 167 ms 54820 KB Output is correct
23 Correct 212 ms 58884 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 38224 KB Output is correct
2 Correct 8 ms 38236 KB Output is correct
3 Correct 151 ms 57056 KB Output is correct
4 Correct 175 ms 61696 KB Output is correct
5 Correct 167 ms 61524 KB Output is correct
6 Correct 175 ms 61476 KB Output is correct
7 Correct 188 ms 61756 KB Output is correct
8 Correct 170 ms 60892 KB Output is correct
9 Correct 184 ms 61500 KB Output is correct
10 Correct 180 ms 60792 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 38224 KB Output is correct
2 Correct 8 ms 38236 KB Output is correct
3 Correct 7 ms 38224 KB Output is correct
4 Correct 7 ms 38224 KB Output is correct
5 Correct 7 ms 38324 KB Output is correct
6 Correct 8 ms 38224 KB Output is correct
7 Correct 9 ms 38224 KB Output is correct
8 Correct 8 ms 38348 KB Output is correct
9 Correct 8 ms 38224 KB Output is correct
10 Correct 7 ms 38224 KB Output is correct
11 Incorrect 7 ms 38412 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 38224 KB Output is correct
2 Correct 6 ms 38224 KB Output is correct
3 Correct 8 ms 38236 KB Output is correct
4 Correct 7 ms 38224 KB Output is correct
5 Correct 7 ms 38224 KB Output is correct
6 Correct 7 ms 38324 KB Output is correct
7 Correct 8 ms 38224 KB Output is correct
8 Correct 9 ms 38224 KB Output is correct
9 Correct 8 ms 38348 KB Output is correct
10 Correct 93 ms 45252 KB Output is correct
11 Correct 108 ms 46788 KB Output is correct
12 Correct 109 ms 48060 KB Output is correct
13 Correct 110 ms 48572 KB Output is correct
14 Correct 116 ms 51132 KB Output is correct
15 Correct 7 ms 38224 KB Output is correct
16 Incorrect 7 ms 38412 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 38224 KB Output is correct
2 Correct 8 ms 38236 KB Output is correct
3 Correct 7 ms 38224 KB Output is correct
4 Correct 7 ms 38224 KB Output is correct
5 Correct 7 ms 38324 KB Output is correct
6 Correct 8 ms 38224 KB Output is correct
7 Correct 9 ms 38224 KB Output is correct
8 Correct 8 ms 38348 KB Output is correct
9 Correct 93 ms 45252 KB Output is correct
10 Correct 108 ms 46788 KB Output is correct
11 Correct 109 ms 48060 KB Output is correct
12 Correct 110 ms 48572 KB Output is correct
13 Correct 116 ms 51132 KB Output is correct
14 Correct 106 ms 47292 KB Output is correct
15 Correct 197 ms 53148 KB Output is correct
16 Correct 188 ms 52844 KB Output is correct
17 Correct 232 ms 53376 KB Output is correct
18 Correct 258 ms 57380 KB Output is correct
19 Correct 151 ms 57056 KB Output is correct
20 Correct 175 ms 61696 KB Output is correct
21 Correct 167 ms 61524 KB Output is correct
22 Correct 175 ms 61476 KB Output is correct
23 Correct 188 ms 61756 KB Output is correct
24 Correct 170 ms 60892 KB Output is correct
25 Correct 184 ms 61500 KB Output is correct
26 Correct 180 ms 60792 KB Output is correct
27 Correct 7 ms 38224 KB Output is correct
28 Incorrect 7 ms 38412 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 38224 KB Output is correct
2 Correct 6 ms 38224 KB Output is correct
3 Correct 8 ms 38236 KB Output is correct
4 Correct 7 ms 38224 KB Output is correct
5 Correct 7 ms 38224 KB Output is correct
6 Correct 7 ms 38324 KB Output is correct
7 Correct 8 ms 38224 KB Output is correct
8 Correct 9 ms 38224 KB Output is correct
9 Correct 8 ms 38348 KB Output is correct
10 Correct 93 ms 45252 KB Output is correct
11 Correct 108 ms 46788 KB Output is correct
12 Correct 109 ms 48060 KB Output is correct
13 Correct 110 ms 48572 KB Output is correct
14 Correct 116 ms 51132 KB Output is correct
15 Correct 106 ms 47292 KB Output is correct
16 Correct 197 ms 53148 KB Output is correct
17 Correct 188 ms 52844 KB Output is correct
18 Correct 232 ms 53376 KB Output is correct
19 Correct 258 ms 57380 KB Output is correct
20 Correct 151 ms 57056 KB Output is correct
21 Correct 175 ms 61696 KB Output is correct
22 Correct 167 ms 61524 KB Output is correct
23 Correct 175 ms 61476 KB Output is correct
24 Correct 188 ms 61756 KB Output is correct
25 Correct 170 ms 60892 KB Output is correct
26 Correct 184 ms 61500 KB Output is correct
27 Correct 180 ms 60792 KB Output is correct
28 Correct 7 ms 38224 KB Output is correct
29 Incorrect 7 ms 38412 KB Output isn't correct
30 Halted 0 ms 0 KB -