oj.uz

답안 #745342

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
745342 2023-05-19T21:49:56 Z Lobo 자매 도시 (APIO20_swap) C++17
0 / 100
 2000 ms 15972 KB 
#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define all(x) x.begin(),x.end()
const int maxn = 2e5+10;
const int lg = 20;

int n, m, gr[maxn], ds[maxn], dsz[maxn], mn[maxn];
vector<int> mn0[maxn];
vector<pair<int,pair<int,int>>> edgs;
// int p[maxn][lg+2], w[maxn][lg+2], h[maxn];
// vector<pair<int,int>> g[maxn];

int find(int u) {
    if(ds[u] == u) return u;
    return ds[u] = find(ds[u]);
}

void join(int u, int v, int id) {
    gr[u]++;
    gr[v]++;
    int mxgr = max(gr[u],gr[v]);

    u = find(u);
    v = find(v);

    if(u == v || mxgr >= 3 || mn[u] != -1 || mn[v] != -1) {
        if(mn0[u].size()) {
            for(auto x : mn0[u]) {
                mn[x] = id;
            }
            mn0[u].clear();
        }
        if(mn0[v].size()) {
            for(auto x : mn0[v]) {
                mn[x] = id;
            }
            mn0[v].clear();
        }
    }
    if(u == v) return;

    if(dsz[u] < dsz[v]) swap(u,v);

    for(auto x : mn0[v]) {
        mn0[u].pb(x);
    }

    dsz[u]+= dsz[v];
    ds[v] = u;
}


// int ds1[maxn], dsz1[maxn];
// int find1(int u) {
//     if(ds1[u] == u) return u;
//     return ds1[u] = find(ds1[u]);
// }

// void join1(int u, int v) {
//     u = find1(u);
//     v = find1(v);
//     if(u == v) return;

//     if(dsz1[u] < dsz1[v]) swap(u,v);
//     dsz1[u]+= dsz1[v];
//     ds1[v] = u;
// }

// void dfs(int u, int ant, int antw) {
//     p[u][0] = ant;
//     w[u][0] = antw;

//     for(int i = 1; i <= lg; i++) {
//         p[u][i] = p[p[u][i-1]][i-1];
//         w[u][i] = max(w[u][i-1],w[p[u][i-1]][i-1]);
//     }

//     for(auto V : g[u]) if(V.fr != ant) {
//         h[V.fr] = h[u]+1;
//         dfs(V.fr,u,V.sc);
//     }
// }

// int lca(int u, int v) {
//     int ans = 0;
//     if(h[u] < h[v]) swap(u,v);

//     for(int i = lg; i >= 0; i--) {
//         if(h[p[u][i]] >= h[v]) {
//             ans = max(ans, w[u][i]);
//             u = p[u][i];
//         }
//     }
//     if(u == v) return ans;

//     for(int i = lg; i >= 0; i--) {
//         if(p[u][i] != p[v][i]) {
//             ans = max(ans,w[u][i]);
//             u = p[u][i];
//             ans = max(ans,w[v][i]);
//             v = p[v][i];
//         }
//     }
//     ans = max(ans, w[u][0]);
//     return ans;
// }

void init(int N, int M, vector<int> U, std::vector<int> V, std::vector<int> W) {
    n = N;
    m = M;

    for(auto i = 0; i < m; i++) {
        edgs.pb(mp(W[i],mp(U[i],V[i])));
    }

    sort(all(edgs));

    // for(int i = 0; i < n; i++) {
    //     gr[i] = 0;
    //     mn[i] = -1;
    //     ds[i] = i;
    //     dsz[i] = 1;
    //     mn0[i].clear();
    //     mn0[i].pb(i);
    // }

    // for(int i = 0; i < m; i++) {
    //     int u = edgs[i].sc.fr;
    //     int v = edgs[i].sc.sc;
    //     if(find(u) != find(v)) {
    //         g[u].pb(mp(v,i));
    //         g[v].pb(mp(u,i));
    //     }
    //     join(u,v,i);
    // }
    // // dfs(0,0,-1);
}

int getMinimumFuelCapacity(int x, int y) {
    for(int i = 0; i < n; i++) {
        gr[i] = 0;
        mn[i] = -1;
        ds[i] = i;
        dsz[i] = 1;
        mn0[i].clear();
        mn0[i].pb(i);
    }

    for(int i = 0; i < m; i++) {
        int u = edgs[i].sc.fr;
        int v = edgs[i].sc.sc;
        // if(find(u) != find(v)) {
        //     g[u].pb(mp(v,i));
        //     g[v].pb(mp(u,i));
        // }
        join(u,v,i);
        if(find(u) == find(v) && mn[u] != -1 && mn[v] != -1) return edgs[i].fr;
    }
    return -1;

}

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 5052 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 4 ms 5076 KB Output is correct
7 Correct 4 ms 5076 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct
9 Correct 59 ms 13828 KB Output is correct
10 Correct 93 ms 15368 KB Output is correct
11 Correct 117 ms 15292 KB Output is correct
12 Correct 127 ms 15972 KB Output is correct
13 Correct 89 ms 13344 KB Output is correct
14 Execution timed out 2062 ms 13988 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Execution timed out 2051 ms 13904 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 5052 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 4 ms 5076 KB Output is correct
7 Correct 4 ms 5076 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct
9 Incorrect 2 ms 4948 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 5052 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 4 ms 5076 KB Output is correct
7 Correct 4 ms 5076 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct
9 Correct 59 ms 13828 KB Output is correct
10 Correct 93 ms 15368 KB Output is correct
11 Correct 117 ms 15292 KB Output is correct
12 Correct 127 ms 15972 KB Output is correct
13 Correct 89 ms 13344 KB Output is correct
14 Execution timed out 2062 ms 13988 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -