oj.uz

답안 #981683

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
981683 2024-05-13T12:56:30 Z Alkaser_ID 자매 도시 (APIO20_swap) C++17
0 / 100
 2000 ms 8648 KB 
#include "swap.h"
using namespace std;
#include <bits/stdc++.h>

vector<vector<int>> adj[100005];
int n,m;
vector<pair<int,pair<int,int>>> v;
void init(int N, int M,
          std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    n=N;m = M;
    for(int i=0;i<m;++i){
        v.push_back({W[i],{U[i],V[i]}});
    }
    sort(v.begin(),v.end());
}
int p[100005],sz[100005]; bool bl[100005];
inline int parent(int a){
    if(a == p[a]) return a;
    return a = parent(p[a]);
}

inline void merg(int x,int y){
    int a = parent(x),b = parent(y);
    if(a == b) return;
    if(sz[b] > sz[a]) swap(a,b);
    sz[a] += sz[b];
    p[b] = a;
    bl[a] = bl[a] | bl[b];
}

int getMinimumFuelCapacity(int X, int Y) {
    for(int i=0;i<n;++i) {
        p[i] = i; sz[i] = 1;
        bl[i] = false;
    }
    int res = -1;
    for(int i=0;i<m;++i){
        int vl = v[i].first;
        int u = v[i].second.first, d = v[i].second.second;
        u = parent(u);d = parent(d);
        if(u == d) bl[u] = true;
        else merg(u,d);
        int px = parent(X),py = parent(Y);
        if(px == py && bl[px]) {
            res = vl;
            break;
        }
    }
    return res;
}

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 3420 KB Output is correct
2 Correct 1 ms 3420 KB Output is correct
3 Correct 1 ms 3420 KB Output is correct
4 Correct 1 ms 3420 KB Output is correct
5 Correct 1 ms 3420 KB Output is correct
6 Correct 2 ms 3420 KB Output is correct
7 Correct 3 ms 3420 KB Output is correct
8 Correct 1 ms 3420 KB Output is correct
9 Correct 29 ms 6868 KB Output is correct
10 Correct 39 ms 7380 KB Output is correct
11 Correct 39 ms 7376 KB Output is correct
12 Correct 42 ms 7372 KB Output is correct
13 Correct 38 ms 7380 KB Output is correct
14 Execution timed out 2028 ms 7116 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

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

Subtask #3
0 / 17.0

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

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 3420 KB Output is correct
2 Correct 1 ms 3420 KB Output is correct
3 Correct 1 ms 3420 KB Output is correct
4 Correct 1 ms 3420 KB Output is correct
5 Correct 1 ms 3420 KB Output is correct
6 Correct 1 ms 3420 KB Output is correct
7 Correct 2 ms 3420 KB Output is correct
8 Correct 3 ms 3420 KB Output is correct
9 Correct 1 ms 3420 KB Output is correct
10 Correct 29 ms 6868 KB Output is correct
11 Correct 39 ms 7380 KB Output is correct
12 Correct 39 ms 7376 KB Output is correct
13 Correct 42 ms 7372 KB Output is correct
14 Correct 38 ms 7380 KB Output is correct
15 Incorrect 2 ms 3420 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 3420 KB Output is correct
2 Correct 1 ms 3420 KB Output is correct
3 Correct 1 ms 3420 KB Output is correct
4 Correct 1 ms 3420 KB Output is correct
5 Correct 1 ms 3420 KB Output is correct
6 Correct 2 ms 3420 KB Output is correct
7 Correct 3 ms 3420 KB Output is correct
8 Correct 1 ms 3420 KB Output is correct
9 Correct 29 ms 6868 KB Output is correct
10 Correct 39 ms 7380 KB Output is correct
11 Correct 39 ms 7376 KB Output is correct
12 Correct 42 ms 7372 KB Output is correct
13 Correct 38 ms 7380 KB Output is correct
14 Execution timed out 2028 ms 7116 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 3420 KB Output is correct
2 Correct 1 ms 3420 KB Output is correct
3 Correct 1 ms 3420 KB Output is correct
4 Correct 1 ms 3420 KB Output is correct
5 Correct 1 ms 3420 KB Output is correct
6 Correct 1 ms 3420 KB Output is correct
7 Correct 2 ms 3420 KB Output is correct
8 Correct 3 ms 3420 KB Output is correct
9 Correct 1 ms 3420 KB Output is correct
10 Correct 29 ms 6868 KB Output is correct
11 Correct 39 ms 7380 KB Output is correct
12 Correct 39 ms 7376 KB Output is correct
13 Correct 42 ms 7372 KB Output is correct
14 Correct 38 ms 7380 KB Output is correct
15 Execution timed out 2028 ms 7116 KB Time limit exceeded
16 Halted 0 ms 0 KB -