Submission #864521

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
864521	2023-10-23 07:12:20	thinknoexit	통행료 (IOI18_highway)	C++17	51 / 100	97 ms	14580 KiB

highway

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
#include "highway.h"
using namespace std;
using ll = long long;
const int N = 90090;
vector<pair<int, int>> adj[N], e;
int n;
int p[N], sz[N];
int fr(int i) {
    return (p[i] == i) ? i : p[i] = fr(p[i]);
}
void dfs(int v, int p = -1) {
    for (auto& x : adj[v]) {
        if (x.first == p) continue;
        e.push_back({ x.second, x.first });
        dfs(x.first, v);
    }
}
void find_pair(int NN, vector<int> U, vector<int> V, int A, int B) {
    n = NN;
    int m = U.size();
    for (int i = 0;i < n;i++) p[i] = i;
    for (int i = 0;i < m;i++) {
        int u = U[i], v = V[i];
        int pu = fr(u), pv = fr(v);
        if (pu != pv) {
            adj[u].push_back({ v,i });
            adj[v].push_back({ u,i });
            p[pu] = pv;
        }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 6 / 6
• Subtask 4: 33 / 33
• Subtask 5: 0 / 18
• Subtask 6: 0 / 31