oj.uz

Submission #1109713

# Submission time Handle Problem Language Result Execution time Memory
1109713 2024-11-07T11:02:21 Z Mike_Vu Swapping Cities (APIO20_swap) C++14
0 / 100
 2000 ms 52520 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));
    memset(h, 0, sizeof(h));
    for (int i = 1; i <= trsz; i++) {
        if (!h[i]) {
            h[i] = 1;
            dfs(i);
        }
    }
//    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
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 38224 KB Output is correct
2 Correct 7 ms 38224 KB Output is correct
3 Correct 7 ms 38224 KB Output is correct
4 Correct 8 ms 38224 KB Output is correct
5 Correct 10 ms 38224 KB Output is correct
6 Correct 9 ms 38224 KB Output is correct
7 Correct 9 ms 38224 KB Output is correct
8 Correct 51 ms 38236 KB Output is correct
9 Correct 517 ms 46888 KB Output is correct
10 Correct 851 ms 49048 KB Output is correct
11 Correct 1025 ms 48832 KB Output is correct
12 Correct 1050 ms 49340 KB Output is correct
13 Execution timed out 2050 ms 49944 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 38224 KB Output is correct
2 Correct 7 ms 38224 KB Output is correct
3 Execution timed out 2023 ms 52520 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

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

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 38224 KB Output is correct
2 Correct 7 ms 38224 KB Output is correct
3 Correct 7 ms 38224 KB Output is correct
4 Correct 7 ms 38224 KB Output is correct
5 Correct 8 ms 38224 KB Output is correct
6 Correct 10 ms 38224 KB Output is correct
7 Correct 9 ms 38224 KB Output is correct
8 Correct 9 ms 38224 KB Output is correct
9 Correct 51 ms 38236 KB Output is correct
10 Correct 517 ms 46888 KB Output is correct
11 Correct 851 ms 49048 KB Output is correct
12 Correct 1025 ms 48832 KB Output is correct
13 Correct 1050 ms 49340 KB Output is correct
14 Execution timed out 2050 ms 49944 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 38224 KB Output is correct
2 Correct 7 ms 38224 KB Output is correct
3 Correct 7 ms 38224 KB Output is correct
4 Correct 8 ms 38224 KB Output is correct
5 Correct 10 ms 38224 KB Output is correct
6 Correct 9 ms 38224 KB Output is correct
7 Correct 9 ms 38224 KB Output is correct
8 Correct 51 ms 38236 KB Output is correct
9 Correct 517 ms 46888 KB Output is correct
10 Correct 851 ms 49048 KB Output is correct
11 Correct 1025 ms 48832 KB Output is correct
12 Correct 1050 ms 49340 KB Output is correct
13 Execution timed out 2050 ms 49944 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 38224 KB Output is correct
2 Correct 7 ms 38224 KB Output is correct
3 Correct 7 ms 38224 KB Output is correct
4 Correct 7 ms 38224 KB Output is correct
5 Correct 8 ms 38224 KB Output is correct
6 Correct 10 ms 38224 KB Output is correct
7 Correct 9 ms 38224 KB Output is correct
8 Correct 9 ms 38224 KB Output is correct
9 Correct 51 ms 38236 KB Output is correct
10 Correct 517 ms 46888 KB Output is correct
11 Correct 851 ms 49048 KB Output is correct
12 Correct 1025 ms 48832 KB Output is correct
13 Correct 1050 ms 49340 KB Output is correct
14 Execution timed out 2050 ms 49944 KB Time limit exceeded
15 Halted 0 ms 0 KB -