oj.uz

Submission #965747

# Submission time Handle Problem Language Result Execution time Memory
965747 2024-04-19T06:49:50 Z pcc Swapping Cities (APIO20_swap) C++17
0 / 100
 2000 ms 15480 KB 
#include "swap.h"

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

#define pii pair<int,int>
#define fs first
#define sc second

const int mxn = 1e5+10;

vector<int> v;
int arr[mxn];
int N,M;
vector<pair<int,pii>> edges;

void init(int NN, int MM,
          std::vector<int> U, std::vector<int> V, std::vector<int> W) {
	N = NN,M = MM;
	for(int i = 0;i<M;i++){
		edges.push_back(make_pair(W[i],pii(U[i],V[i])));
	}
	sort(edges.begin(),edges.end());
	return;
}

namespace BIS{
	vector<int> paths[mxn];
	int dp[mxn];
	queue<int> q;
	int deg[mxn];

	void bfs(int s,int t,int tag){
		q.push(s);
		dp[s] |= tag;
		while(!q.empty()){
			auto now = q.front();
			q.pop();
			if(now == t)continue;
			for(auto nxt:paths[now]){
				if(!(dp[nxt]&tag)){
					dp[nxt]|=tag;
					q.push(nxt);
				}
			}
		}
		return;
	}

	bool check(int id,int s,int t){
		memset(dp,0,sizeof(dp));
		memset(deg,0,sizeof(deg));
		for(int i = 0;i<N;i++)paths[i].clear();
		for(int i = 0;i<=min(M-1,id);i++){
			paths[edges[i].sc.fs].push_back(edges[i].sc.sc);
			paths[edges[i].sc.sc].push_back(edges[i].sc.fs);
		}
		bfs(s,t,1);
		bfs(t,s,2);
		if(dp[s] != 3||dp[t] != 3)return false;
		for(int i = 0;i<N;i++){
			if(dp[i] == 3){
				for(auto nxt:paths[i])deg[nxt]++;
			}
		}
		bool flag = false;
		for(int i = 0;i<N;i++){
			if(dp[i] == 3&&i != s&&i != t&&deg[i] != 2)flag = true;
		}
		if(deg[s] != 1||deg[t] != 1)flag = true;
		if(paths[s].size()>=3||paths[t].size()>=3)flag = true;
		return flag;
	}
}

int getMinimumFuelCapacity(int X, int Y) {
	int l = 0,r = M;
	while(l != r){
		int mid = (l+r)>>1;
		if(BIS::check(mid,X,Y))r = mid;
		else l = mid+1;
		//cout<<X<<' '<<Y<<' '<<edges[mid].fs<<":"<<BIS::check(mid,X,Y)<<endl;
	}
	if(r>=M)return -1;
	return edges[l].fs;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3420 KB Output is correct
2 Correct 1 ms 3420 KB Output is correct
3 Correct 1 ms 3420 KB Output is correct
4 Correct 2 ms 3420 KB Output is correct
5 Correct 2 ms 3648 KB Output is correct
6 Correct 2 ms 3420 KB Output is correct
7 Correct 2 ms 3420 KB Output is correct
8 Correct 3 ms 3652 KB Output is correct
9 Correct 73 ms 9520 KB Output is correct
10 Correct 135 ms 10852 KB Output is correct
11 Correct 159 ms 10560 KB Output is correct
12 Correct 168 ms 11056 KB Output is correct
13 Correct 229 ms 11168 KB Output is correct
14 Execution timed out 2029 ms 9768 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3420 KB Output is correct
2 Correct 1 ms 3420 KB Output is correct
3 Execution timed out 2009 ms 15480 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3420 KB Output is correct
2 Correct 1 ms 3420 KB Output is correct
3 Correct 1 ms 3420 KB Output is correct
4 Correct 2 ms 3420 KB Output is correct
5 Correct 2 ms 3648 KB Output is correct
6 Correct 2 ms 3420 KB Output is correct
7 Correct 2 ms 3420 KB Output is correct
8 Correct 3 ms 3652 KB Output is correct
9 Correct 1 ms 3672 KB Output is correct
10 Correct 3 ms 3420 KB Output is correct
11 Correct 3 ms 3420 KB Output is correct
12 Correct 3 ms 3416 KB Output is correct
13 Correct 3 ms 3420 KB Output is correct
14 Correct 4 ms 3444 KB Output is correct
15 Incorrect 3 ms 3420 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3672 KB Output is correct
2 Correct 1 ms 3420 KB Output is correct
3 Correct 1 ms 3420 KB Output is correct
4 Correct 1 ms 3420 KB Output is correct
5 Correct 2 ms 3420 KB Output is correct
6 Correct 2 ms 3648 KB Output is correct
7 Correct 2 ms 3420 KB Output is correct
8 Correct 2 ms 3420 KB Output is correct
9 Correct 3 ms 3652 KB Output is correct
10 Correct 73 ms 9520 KB Output is correct
11 Correct 135 ms 10852 KB Output is correct
12 Correct 159 ms 10560 KB Output is correct
13 Correct 168 ms 11056 KB Output is correct
14 Correct 229 ms 11168 KB Output is correct
15 Correct 3 ms 3420 KB Output is correct
16 Correct 3 ms 3420 KB Output is correct
17 Correct 3 ms 3416 KB Output is correct
18 Correct 3 ms 3420 KB Output is correct
19 Correct 4 ms 3444 KB Output is correct
20 Incorrect 3 ms 3420 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3420 KB Output is correct
2 Correct 1 ms 3420 KB Output is correct
3 Correct 1 ms 3420 KB Output is correct
4 Correct 2 ms 3420 KB Output is correct
5 Correct 2 ms 3648 KB Output is correct
6 Correct 2 ms 3420 KB Output is correct
7 Correct 2 ms 3420 KB Output is correct
8 Correct 3 ms 3652 KB Output is correct
9 Correct 73 ms 9520 KB Output is correct
10 Correct 135 ms 10852 KB Output is correct
11 Correct 159 ms 10560 KB Output is correct
12 Correct 168 ms 11056 KB Output is correct
13 Correct 229 ms 11168 KB Output is correct
14 Execution timed out 2029 ms 9768 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3672 KB Output is correct
2 Correct 1 ms 3420 KB Output is correct
3 Correct 1 ms 3420 KB Output is correct
4 Correct 1 ms 3420 KB Output is correct
5 Correct 2 ms 3420 KB Output is correct
6 Correct 2 ms 3648 KB Output is correct
7 Correct 2 ms 3420 KB Output is correct
8 Correct 2 ms 3420 KB Output is correct
9 Correct 3 ms 3652 KB Output is correct
10 Correct 73 ms 9520 KB Output is correct
11 Correct 135 ms 10852 KB Output is correct
12 Correct 159 ms 10560 KB Output is correct
13 Correct 168 ms 11056 KB Output is correct
14 Correct 229 ms 11168 KB Output is correct
15 Execution timed out 2029 ms 9768 KB Time limit exceeded
16 Halted 0 ms 0 KB -