oj.uz

Submission #965758

# Submission time Handle Problem Language Result Execution time Memory
965758 2024-04-19T07:01:03 Z pcc Swapping Cities (APIO20_swap) C++17
0 / 100
 2000 ms 14956 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 = 2e5+10;

vector<int> v;
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)continue;
				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 2 ms 6488 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 2 ms 6492 KB Output is correct
4 Correct 4 ms 6492 KB Output is correct
5 Correct 5 ms 6748 KB Output is correct
6 Correct 4 ms 6748 KB Output is correct
7 Correct 5 ms 6748 KB Output is correct
8 Correct 5 ms 6748 KB Output is correct
9 Correct 76 ms 11000 KB Output is correct
10 Correct 132 ms 11876 KB Output is correct
11 Correct 162 ms 11640 KB Output is correct
12 Correct 169 ms 12088 KB Output is correct
13 Correct 231 ms 12180 KB Output is correct
14 Execution timed out 2028 ms 11056 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6488 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Execution timed out 2052 ms 14956 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6488 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 2 ms 6492 KB Output is correct
4 Correct 4 ms 6492 KB Output is correct
5 Correct 5 ms 6748 KB Output is correct
6 Correct 4 ms 6748 KB Output is correct
7 Correct 5 ms 6748 KB Output is correct
8 Correct 5 ms 6748 KB Output is correct
9 Correct 2 ms 6488 KB Output is correct
10 Correct 4 ms 6744 KB Output is correct
11 Correct 4 ms 6748 KB Output is correct
12 Correct 4 ms 6748 KB Output is correct
13 Correct 5 ms 6748 KB Output is correct
14 Correct 4 ms 6748 KB Output is correct
15 Incorrect 4 ms 6748 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6488 KB Output is correct
2 Correct 2 ms 6488 KB Output is correct
3 Correct 2 ms 6492 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 4 ms 6492 KB Output is correct
6 Correct 5 ms 6748 KB Output is correct
7 Correct 4 ms 6748 KB Output is correct
8 Correct 5 ms 6748 KB Output is correct
9 Correct 5 ms 6748 KB Output is correct
10 Correct 76 ms 11000 KB Output is correct
11 Correct 132 ms 11876 KB Output is correct
12 Correct 162 ms 11640 KB Output is correct
13 Correct 169 ms 12088 KB Output is correct
14 Correct 231 ms 12180 KB Output is correct
15 Correct 4 ms 6744 KB Output is correct
16 Correct 4 ms 6748 KB Output is correct
17 Correct 4 ms 6748 KB Output is correct
18 Correct 5 ms 6748 KB Output is correct
19 Correct 4 ms 6748 KB Output is correct
20 Incorrect 4 ms 6748 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6488 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 2 ms 6492 KB Output is correct
4 Correct 4 ms 6492 KB Output is correct
5 Correct 5 ms 6748 KB Output is correct
6 Correct 4 ms 6748 KB Output is correct
7 Correct 5 ms 6748 KB Output is correct
8 Correct 5 ms 6748 KB Output is correct
9 Correct 76 ms 11000 KB Output is correct
10 Correct 132 ms 11876 KB Output is correct
11 Correct 162 ms 11640 KB Output is correct
12 Correct 169 ms 12088 KB Output is correct
13 Correct 231 ms 12180 KB Output is correct
14 Execution timed out 2028 ms 11056 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6488 KB Output is correct
2 Correct 2 ms 6488 KB Output is correct
3 Correct 2 ms 6492 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 4 ms 6492 KB Output is correct
6 Correct 5 ms 6748 KB Output is correct
7 Correct 4 ms 6748 KB Output is correct
8 Correct 5 ms 6748 KB Output is correct
9 Correct 5 ms 6748 KB Output is correct
10 Correct 76 ms 11000 KB Output is correct
11 Correct 132 ms 11876 KB Output is correct
12 Correct 162 ms 11640 KB Output is correct
13 Correct 169 ms 12088 KB Output is correct
14 Correct 231 ms 12180 KB Output is correct
15 Execution timed out 2028 ms 11056 KB Time limit exceeded
16 Halted 0 ms 0 KB -