# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
385173 | 2021-04-03T12:51:13 Z | kwongweng | 자매 도시 (APIO20_swap) | C++17 | 118 ms | 13944 KB |
#include "swap.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> vi; typedef pair<int, int> ii; typedef vector<ii> vii; #define FOR(i, a, b) for(int i = a; i < b; i++) #define ROF(i, a, b) for(int i = a; i >= b; i--) #define ms memset #define pb push_back #define F first #define S second int l = 0; vector<pair<int, ii>> edges; vi p, r, deg, maxi, num, sz; void init(int n, int m, vi U, vi V, vi W) { FOR(i, 0, m){ edges.pb({W[i], {U[i], V[i]}}); l = max(l, W[i]); } if (m == n-1) l = -1; sort(edges.begin(), edges.end()); p.resize(n); r.resize(n); deg.resize(n); maxi.resize(n); num.resize(n); sz.resize(n); } int get(int a){ return p[a] = (p[a] == a ? a : get(p[a])); } void Union(int c, int d){ int a = get(c), b = get(d); if (a == b) return; if (r[a] == r[b]) r[a]++; if (r[a] > r[b]){ p[b] = a; maxi[a] = max(maxi[b], maxi[a]); num[a] += num[b]; sz[a] += sz[b]; }else{ p[a] = b; maxi[b] = max(maxi[a], maxi[b]); num[b] += num[a]; sz[b] += sz[a]; } } int getMinimumFuelCapacity(int x, int y) { return l; FOR(i, 0, p.size()) p[i] = i; FOR(i, 0, r.size()){ r[i] = 0; deg[i] = 0, maxi[i] = 0; num[i] = 0; sz[i] = 1; } FOR(i, 0, edges.size()){ int a = edges[i].S.F, b = edges[i].S.S; Union(a, b); deg[a]++; deg[b]++; maxi[get(a)] = max(maxi[get(a)], deg[a]); maxi[get(b)] = max(maxi[get(b)], deg[b]); num[get(a)]++; if (get(x) != get(y)) continue; if (maxi[get(x)] < 3 && num[get(x)] < sz[get(x)]) continue; return edges[i].F; } return -1; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 364 KB | Output is correct |
2 | Correct | 1 ms | 364 KB | Output is correct |
3 | Correct | 1 ms | 364 KB | Output is correct |
4 | Correct | 2 ms | 364 KB | Output is correct |
5 | Correct | 1 ms | 364 KB | Output is correct |
6 | Correct | 1 ms | 364 KB | Output is correct |
7 | Correct | 1 ms | 364 KB | Output is correct |
8 | Correct | 2 ms | 364 KB | Output is correct |
9 | Correct | 38 ms | 4960 KB | Output is correct |
10 | Correct | 49 ms | 5984 KB | Output is correct |
11 | Correct | 45 ms | 5856 KB | Output is correct |
12 | Correct | 47 ms | 6240 KB | Output is correct |
13 | Correct | 49 ms | 6240 KB | Output is correct |
14 | Correct | 44 ms | 5088 KB | Output is correct |
15 | Correct | 113 ms | 12392 KB | Output is correct |
16 | Correct | 110 ms | 11920 KB | Output is correct |
17 | Correct | 115 ms | 12356 KB | Output is correct |
18 | Correct | 117 ms | 12356 KB | Output is correct |
19 | Correct | 63 ms | 6828 KB | Output is correct |
20 | Correct | 111 ms | 13148 KB | Output is correct |
21 | Correct | 118 ms | 13336 KB | Output is correct |
22 | Correct | 117 ms | 13764 KB | Output is correct |
23 | Correct | 117 ms | 13944 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 364 KB | Output is correct |
2 | Correct | 1 ms | 364 KB | Output is correct |
3 | Incorrect | 104 ms | 7556 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 364 KB | Output is correct |
2 | Correct | 1 ms | 364 KB | Output is correct |
3 | Correct | 1 ms | 364 KB | Output is correct |
4 | Correct | 2 ms | 364 KB | Output is correct |
5 | Correct | 1 ms | 364 KB | Output is correct |
6 | Correct | 1 ms | 364 KB | Output is correct |
7 | Correct | 1 ms | 364 KB | Output is correct |
8 | Correct | 2 ms | 364 KB | Output is correct |
9 | Incorrect | 1 ms | 512 KB | Output isn't correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 512 KB | Output isn't correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 364 KB | Output is correct |
2 | Correct | 1 ms | 364 KB | Output is correct |
3 | Correct | 1 ms | 364 KB | Output is correct |
4 | Correct | 2 ms | 364 KB | Output is correct |
5 | Correct | 1 ms | 364 KB | Output is correct |
6 | Correct | 1 ms | 364 KB | Output is correct |
7 | Correct | 1 ms | 364 KB | Output is correct |
8 | Correct | 2 ms | 364 KB | Output is correct |
9 | Correct | 38 ms | 4960 KB | Output is correct |
10 | Correct | 49 ms | 5984 KB | Output is correct |
11 | Correct | 45 ms | 5856 KB | Output is correct |
12 | Correct | 47 ms | 6240 KB | Output is correct |
13 | Correct | 49 ms | 6240 KB | Output is correct |
14 | Correct | 44 ms | 5088 KB | Output is correct |
15 | Correct | 113 ms | 12392 KB | Output is correct |
16 | Correct | 110 ms | 11920 KB | Output is correct |
17 | Correct | 115 ms | 12356 KB | Output is correct |
18 | Correct | 117 ms | 12356 KB | Output is correct |
19 | Incorrect | 104 ms | 7556 KB | Output isn't correct |
20 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 512 KB | Output isn't correct |