oj.uz

Submission #434466

# Submission time Handle Problem Language Result Execution time Memory
434466 2021-06-21T10:41:14 Z dqhungdl Swapping Cities (APIO20_swap) C++17
0 / 100
 1683 ms 524292 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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