Submission #967081

#	Time	Username	Problem	Language	Result	Execution time	Memory
967081		fcmalkcin	Swapping Cities (APIO20_swap)	C++17	0 / 100	79 ms	17148 KiB

swap

#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++){
			if(deg[i])cnt[deg[i]]++;
		}
		if(*max_element(cnt+3,cnt+mxn) == 0&&cnt[1] == 2)return false;
		return true;
	}
}
 
int getMinimumFuelCapacity(int X, int Y) {
	return -1;
}

• Subtask 1: 0 / 6
• Subtask 2: 0 / 7
• Subtask 3: 0 / 17
• Subtask 4: 0 / 20
• Subtask 5: 0 / 23
• Subtask 6: 0 / 27