oj.uz

답안 #1109713

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1109713 2024-11-07T11:02:21 Z Mike_Vu 자매 도시 (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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -