oj.uz

Submission #965983

# Submission time Handle Problem Language Result Execution time Memory
965983 2024-04-19T08:58:12 Z pcc Swapping Cities (APIO20_swap) C++17
0 / 100
 2000 ms 15468 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;
	}

	int cnt[mxn];
	bool check(int id,int s,int t){
		memset(dp,0,sizeof(dp));
		memset(deg,0,sizeof(deg));
		memset(cnt,0,sizeof(cnt));
		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,N,1);
		if(!dp[t])return false;
		for(int i = 0;i<N;i++){
			if(dp[i]){
				for(auto nxt:paths[i])deg[nxt]++;
			}
		}
		return false;
		for(int i = 0;i<N;i++){
			cnt[deg[i]]++;
		}
		if(*max_element(cnt+3,cnt+N) == 0&&cnt[1] == 2)return false;
		return true;
	}
}

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 7256 KB Output is correct
2 Correct 2 ms 7260 KB Output is correct
3 Correct 2 ms 7260 KB Output is correct
4 Correct 4 ms 7516 KB Output is correct
5 Correct 4 ms 7532 KB Output is correct
6 Correct 5 ms 7516 KB Output is correct
7 Correct 4 ms 7516 KB Output is correct
8 Correct 5 ms 7516 KB Output is correct
9 Correct 66 ms 11576 KB Output is correct
10 Correct 128 ms 12740 KB Output is correct
11 Correct 144 ms 12652 KB Output is correct
12 Correct 182 ms 13192 KB Output is correct
13 Correct 190 ms 12812 KB Output is correct
14 Execution timed out 2015 ms 11816 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 7256 KB Output is correct
2 Correct 2 ms 7260 KB Output is correct
3 Execution timed out 2101 ms 15468 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 7256 KB Output is correct
2 Correct 2 ms 7260 KB Output is correct
3 Correct 2 ms 7260 KB Output is correct
4 Correct 4 ms 7516 KB Output is correct
5 Correct 4 ms 7532 KB Output is correct
6 Correct 5 ms 7516 KB Output is correct
7 Correct 4 ms 7516 KB Output is correct
8 Correct 5 ms 7516 KB Output is correct
9 Incorrect 2 ms 7256 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 7256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7256 KB Output is correct
2 Correct 2 ms 7260 KB Output is correct
3 Correct 2 ms 7260 KB Output is correct
4 Correct 4 ms 7516 KB Output is correct
5 Correct 4 ms 7532 KB Output is correct
6 Correct 5 ms 7516 KB Output is correct
7 Correct 4 ms 7516 KB Output is correct
8 Correct 5 ms 7516 KB Output is correct
9 Correct 66 ms 11576 KB Output is correct
10 Correct 128 ms 12740 KB Output is correct
11 Correct 144 ms 12652 KB Output is correct
12 Correct 182 ms 13192 KB Output is correct
13 Correct 190 ms 12812 KB Output is correct
14 Execution timed out 2015 ms 11816 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 7256 KB Output isn't correct
2 Halted 0 ms 0 KB -