답안 #563724

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
563724	2022-05-18T04:05:36 Z	8e7	자매 도시 (APIO20_swap)	C++17	6 / 100	256 ms	20868 KB

swap

//Challenge: Accepted
#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 100005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
struct edge{
	int u, v, w;
	edge(){u = v = w = 0;}
	edge(int a, int b, int c){u = a, v = b, w = c;}
};
vector<pii> ev[maxn]; //events
int valid[maxn];
struct DSU{
	int par[maxn], deg[maxn];
	bool mark[maxn];
	pii leaf[maxn];
	int ti;
	void init(int n) {
		for (int i = 0;i < n;i++) {
			ev[i].push_back({-1, i});
			par[i] = i, deg[i] = 0, mark[i] = 0, leaf[i] = {i, 0}; 
			valid[i] = 1<<30;
		}
		ti = 0;
	}
	int find(int a) {
		if (a == par[a]) return a;
		int ret = find(par[a]);
		if (ret != par[a]) ev[a].push_back({ti, ret});
		par[a] = ret;
		return ret;
	}
	void Union(int a, int b) {
		int pa = find(a), pb = find(b);
		deg[a]++, deg[b]++;
		if (deg[a] >= 3 || deg[b] >= 3 || mark[pa]) {
			valid[pb] = min(valid[pb], ti);
			mark[pb] = 1;
		}
		if (deg[a] == 1 && deg[b] == 1) {
			leaf[pb] = {a, b};
		} else {
			if (pa == pb && (leaf[pa] == make_pair(a, b) || leaf[pa] == make_pair(b, a))) {
				valid[pb] = min(valid[pb], ti);
				mark[pb] = 1;
			}
			if (pa != pb) {
				pii p;
				if (deg[leaf[pa].ff] == 1) p.ff = leaf[pa].ff;
				else p.ff = leaf[pa].ss;
				if (deg[leaf[pb].ff] == 1) p.ss = leaf[pb].ff;
				else p.ss = leaf[pb].ss;
				leaf[pb] = p;
			}
		}
		ev[pa].push_back({ti, pb});
		par[pa] = pb;
	}
} d;
vector<edge> ed;
int n, m;
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
	n = N, m = M;
	for (int i = 0;i < m;i++) ed.push_back(edge(U[i], V[i], W[i]));
	sort(ed.begin(), ed.end(), [&] (edge x, edge y){return x.w < y.w;});
	d.init(n);
	for (int i = 0;i < m;i++) {
		d.Union(ed[i].u, ed[i].v);
		d.ti++;
	}
}
int pfind(int a, int ti) {
	int ind = upper_bound(ev[a].begin(), ev[a].end(), make_pair(ti, 1<<30)) - ev[a].begin() - 1;	
	if (ev[a][ind].ss == a) return a;
	return ev[a][ind].ss = pfind(ev[a][ind].ss, ti);
}
int getMinimumFuelCapacity(int X, int Y) {
	int low = 0, up = m;
	while (low < up - 1) {
		int mid = (low + up) / 2;
		int vx = pfind(X, mid), vy = pfind(Y, mid);
		if (vx == vy && valid[vx] <= mid) up = mid;
		else low = mid;
	}
	if (up == m) return -1;
	else return ed[up].w;
}

Subtask #1
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	3412 KB	Output is correct
2	Correct	2 ms	3412 KB	Output is correct
3	Correct	2 ms	3412 KB	Output is correct
4	Correct	2 ms	3540 KB	Output is correct
5	Correct	2 ms	3412 KB	Output is correct
6	Correct	2 ms	3412 KB	Output is correct
7	Correct	2 ms	3424 KB	Output is correct
8	Correct	3 ms	3448 KB	Output is correct
9	Correct	47 ms	10508 KB	Output is correct
10	Correct	62 ms	12036 KB	Output is correct
11	Correct	60 ms	11980 KB	Output is correct
12	Correct	63 ms	12404 KB	Output is correct
13	Correct	64 ms	12752 KB	Output is correct
14	Correct	84 ms	10648 KB	Output is correct
15	Correct	256 ms	13956 KB	Output is correct
16	Correct	244 ms	13676 KB	Output is correct
17	Correct	248 ms	14304 KB	Output is correct
18	Correct	240 ms	14564 KB	Output is correct
19	Correct	127 ms	10296 KB	Output is correct
20	Correct	249 ms	19272 KB	Output is correct
21	Correct	241 ms	19320 KB	Output is correct
22	Correct	256 ms	19988 KB	Output is correct
23	Correct	243 ms	20868 KB	Output is correct

Subtask #2
0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	3412 KB	Output is correct
2	Correct	2 ms	3412 KB	Output is correct
3	Incorrect	244 ms	16240 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #3
0 / 17.0

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

Subtask #4
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	3412 KB	Output is correct
2	Correct	1 ms	3412 KB	Output is correct
3	Correct	2 ms	3412 KB	Output is correct
4	Correct	2 ms	3412 KB	Output is correct
5	Correct	2 ms	3540 KB	Output is correct
6	Correct	2 ms	3412 KB	Output is correct
7	Correct	2 ms	3412 KB	Output is correct
8	Correct	2 ms	3424 KB	Output is correct
9	Correct	3 ms	3448 KB	Output is correct
10	Correct	47 ms	10508 KB	Output is correct
11	Correct	62 ms	12036 KB	Output is correct
12	Correct	60 ms	11980 KB	Output is correct
13	Correct	63 ms	12404 KB	Output is correct
14	Correct	64 ms	12752 KB	Output is correct
15	Incorrect	3 ms	3540 KB	Output isn't correct
16	Halted	0 ms	0 KB	-

Subtask #5
0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	3412 KB	Output is correct
2	Correct	2 ms	3412 KB	Output is correct
3	Correct	2 ms	3412 KB	Output is correct
4	Correct	2 ms	3540 KB	Output is correct
5	Correct	2 ms	3412 KB	Output is correct
6	Correct	2 ms	3412 KB	Output is correct
7	Correct	2 ms	3424 KB	Output is correct
8	Correct	3 ms	3448 KB	Output is correct
9	Correct	47 ms	10508 KB	Output is correct
10	Correct	62 ms	12036 KB	Output is correct
11	Correct	60 ms	11980 KB	Output is correct
12	Correct	63 ms	12404 KB	Output is correct
13	Correct	64 ms	12752 KB	Output is correct
14	Correct	84 ms	10648 KB	Output is correct
15	Correct	256 ms	13956 KB	Output is correct
16	Correct	244 ms	13676 KB	Output is correct
17	Correct	248 ms	14304 KB	Output is correct
18	Correct	240 ms	14564 KB	Output is correct
19	Incorrect	244 ms	16240 KB	Output isn't correct
20	Halted	0 ms	0 KB	-

Subtask #6
0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	3412 KB	Output is correct
2	Correct	1 ms	3412 KB	Output is correct
3	Correct	2 ms	3412 KB	Output is correct
4	Correct	2 ms	3412 KB	Output is correct
5	Correct	2 ms	3540 KB	Output is correct
6	Correct	2 ms	3412 KB	Output is correct
7	Correct	2 ms	3412 KB	Output is correct
8	Correct	2 ms	3424 KB	Output is correct
9	Correct	3 ms	3448 KB	Output is correct
10	Correct	47 ms	10508 KB	Output is correct
11	Correct	62 ms	12036 KB	Output is correct
12	Correct	60 ms	11980 KB	Output is correct
13	Correct	63 ms	12404 KB	Output is correct
14	Correct	64 ms	12752 KB	Output is correct
15	Correct	84 ms	10648 KB	Output is correct
16	Correct	256 ms	13956 KB	Output is correct
17	Correct	244 ms	13676 KB	Output is correct
18	Correct	248 ms	14304 KB	Output is correct
19	Correct	240 ms	14564 KB	Output is correct
20	Incorrect	244 ms	16240 KB	Output isn't correct
21	Halted	0 ms	0 KB	-

답안 #563724

Compilation message

Subtask #1 6.0 / 6.0

Subtask #2 0 / 7.0

Subtask #3 0 / 17.0

Subtask #4 0 / 20.0

Subtask #5 0 / 23.0

Subtask #6 0 / 27.0

Subtask #1
6.0 / 6.0

Subtask #2
0 / 7.0

Subtask #3
0 / 17.0

Subtask #4
0 / 20.0

Subtask #5
0 / 23.0

Subtask #6
0 / 27.0