답안 #434466

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
434466	2021-06-21T10:41:14 Z	dqhungdl	자매 도시 (APIO20_swap)	C++17	0 / 100	1683 ms	524292 KB

swap

#include "swap.h"

#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int> ii;
typedef pair<int,ii> iii;
const int MAX=1e5+5;
int P[MAX];
bool isTree[MAX];
vector<int> S[MAX];
vector<iii> edges,history[MAX];

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

void merge(int u,int v,int w) {
	if(S[u].size()>S[v].size())
		swap(u,v);
	P[v]=u;
	int newIsTree=isTree[u]&isTree[v];
	while(S[v].size()>0) {
		int tmp=S[v].back();
		S[v].pop_back();
		S[u].push_back(tmp);
		history[tmp].push_back({w,{u,newIsTree}});
	}
}

void init(int N, int M,
          std::vector<int> U, std::vector<int> V, std::vector<int> W) {
	for(int i=0;i<M;i++)
		edges.push_back({W[i],{U[i],V[i]}});
	sort(edges.begin(),edges.end());
	for(int i=0;i<N;i++) {
		P[i]=i;
		isTree[i]=true;
		S[i].push_back(i);
		history[i].push_back({2e9,{i,false}});
	}
	for(iii edge:edges) {
		int u=find(edge.second.first),v=find(edge.second.second),w=edge.first;
		if(u!=v)
			merge(u,v,w);
		else if(isTree[u]) {
			isTree[u]=false;
			for(int tmp:S[u])
				history[tmp].push_back({w,{u,false}});
		}
	}
}

vector<ii> getHistory(int u) {
	vector<ii> rs;
	for(iii his:history[u])
		if(!his.second.second)
			rs.push_back({his.first,his.second.first});
	return rs;
}

int getMinimumFuelCapacity(int X, int Y) {
	vector<ii> hisX=getHistory(X),hisY=getHistory(Y);
	int rs=-1;
	while(hisX.size()>0&&hisY.size()>0&&hisX.back().second==hisY.back().second) {
		rs=min(hisX.back().first,hisY.back().first);
		hisX.pop_back(),hisY.pop_back();
	}
	return rs;
}

Subtask #1

0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	4992 KB	Output is correct
2	Correct	3 ms	4940 KB	Output is correct
3	Correct	3 ms	4940 KB	Output is correct
4	Correct	4 ms	5024 KB	Output is correct
5	Correct	4 ms	5264 KB	Output is correct
6	Correct	5 ms	5324 KB	Output is correct
7	Correct	5 ms	5268 KB	Output is correct
8	Correct	12 ms	10828 KB	Output is correct
9	Correct	302 ms	44940 KB	Output is correct
10	Correct	390 ms	55468 KB	Output is correct
11	Correct	335 ms	55664 KB	Output is correct
12	Correct	432 ms	57932 KB	Output is correct
13	Runtime error	1683 ms	524292 KB	Execution killed with signal 9

Subtask #2

0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	4992 KB	Output is correct
2	Correct	3 ms	4940 KB	Output is correct
3	Runtime error	1645 ms	524292 KB	Execution killed with signal 9
4	Halted	0 ms	0 KB	-

Subtask #3

0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	4992 KB	Output is correct
2	Correct	3 ms	4940 KB	Output is correct
3	Correct	3 ms	4940 KB	Output is correct
4	Correct	4 ms	5024 KB	Output is correct
5	Correct	4 ms	5264 KB	Output is correct
6	Correct	5 ms	5324 KB	Output is correct
7	Correct	5 ms	5268 KB	Output is correct
8	Correct	12 ms	10828 KB	Output is correct
9	Correct	3 ms	4940 KB	Output is correct
10	Incorrect	7 ms	6224 KB	Output isn't correct
11	Halted	0 ms	0 KB	-

Subtask #4

0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	4940 KB	Output is correct
2	Correct	4 ms	4992 KB	Output is correct
3	Correct	3 ms	4940 KB	Output is correct
4	Correct	3 ms	4940 KB	Output is correct
5	Correct	4 ms	5024 KB	Output is correct
6	Correct	4 ms	5264 KB	Output is correct
7	Correct	5 ms	5324 KB	Output is correct
8	Correct	5 ms	5268 KB	Output is correct
9	Correct	12 ms	10828 KB	Output is correct
10	Correct	302 ms	44940 KB	Output is correct
11	Correct	390 ms	55468 KB	Output is correct
12	Correct	335 ms	55664 KB	Output is correct
13	Correct	432 ms	57932 KB	Output is correct
14	Runtime error	1683 ms	524292 KB	Execution killed with signal 9

Subtask #5

0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	4992 KB	Output is correct
2	Correct	3 ms	4940 KB	Output is correct
3	Correct	3 ms	4940 KB	Output is correct
4	Correct	4 ms	5024 KB	Output is correct
5	Correct	4 ms	5264 KB	Output is correct
6	Correct	5 ms	5324 KB	Output is correct
7	Correct	5 ms	5268 KB	Output is correct
8	Correct	12 ms	10828 KB	Output is correct
9	Correct	302 ms	44940 KB	Output is correct
10	Correct	390 ms	55468 KB	Output is correct
11	Correct	335 ms	55664 KB	Output is correct
12	Correct	432 ms	57932 KB	Output is correct
13	Runtime error	1683 ms	524292 KB	Execution killed with signal 9

Subtask #6

0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	4940 KB	Output is correct
2	Correct	4 ms	4992 KB	Output is correct
3	Correct	3 ms	4940 KB	Output is correct
4	Correct	3 ms	4940 KB	Output is correct
5	Correct	4 ms	5024 KB	Output is correct
6	Correct	4 ms	5264 KB	Output is correct
7	Correct	5 ms	5324 KB	Output is correct
8	Correct	5 ms	5268 KB	Output is correct
9	Correct	12 ms	10828 KB	Output is correct
10	Correct	302 ms	44940 KB	Output is correct
11	Correct	390 ms	55468 KB	Output is correct
12	Correct	335 ms	55664 KB	Output is correct
13	Correct	432 ms	57932 KB	Output is correct
14	Runtime error	1683 ms	524292 KB	Execution killed with signal 9