oj.uz

Submission #965980

# Submission time Handle Problem Language Result Execution time Memory
965980 2024-04-19T08:57:27 Z pcc Swapping Cities (APIO20_swap) C++17
0 / 100
 8 ms 14680 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]++;
			}
		}
		for(int i = 0;i<N;i++){
			assert(deg[i]<N);
			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 Runtime error 8 ms 14680 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 14680 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 14680 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 14680 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 14680 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 14680 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -