Submission #966049

#	Time	Username	Problem	Language	Result	Execution time	Memory
966049		pcc	Swapping Cities (APIO20_swap)	C++17	100 / 100	312 ms	100768 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 = 4e5+10;

vector<int> v;
int N,M;
vector<pair<int,pii>> edges;
vector<int> tree[mxn];
int dp[mxn][20];
int par[mxn][20];
pii val[mxn];
int dep[mxn];
int rt;

namespace INIT{
	int deg[mxn];
	struct DSU{
		bool chn[mxn];
		int cnt[mxn][2];
		int head[mxn];
		int sz[mxn],dsu[mxn];
		void init(int n){
			for(int i = 0;i<=n;i++){
				dsu[i] = i,sz[i] = 1;
				chn[i] = true;
				cnt[i][0] = 1;
				head[i] = i;
			}
		}
		int root(int k){
			return k == dsu[k]?k:dsu[k] = root(dsu[k]);
		}

		void upd(int now){
			int r = root(now);
			if(deg[now]<2){
				cnt[r][deg[now]]--;
				deg[now]++;
				if(deg[now]<2)cnt[r][deg[now]]++;
			}
			else{
				chn[r] = false;
			}
			return;
		}

		void check(int r){
			r = root(r);
			if(cnt[r][1]>2)chn[r] = false;
			return;
		}

		void onion(int a,int b){
			int ra = root(a),rb = root(b);
			if(ra == rb){
				chn[ra] = false;
				return;
			}
			if(sz[ra]<sz[rb]){
				swap(a,b);
				swap(ra,rb);
			}
			if(!chn[ra]||!chn[rb])chn[ra] = false;
			sz[ra] += sz[rb];
			dsu[rb] = ra;
			for(int i = 0;i<2;i++)cnt[ra][i] += cnt[rb][i];
			upd(a);
			upd(b);
			check(ra);
			return;
		}
	};

	DSU dsu;

	void dfs(int now){
		dp[now][0] = val[now].sc;
		for(int i = 1;i<20;i++){
			par[now][i] = par[par[now][i-1]][i-1];
			dp[now][i] = dp[par[now][i-1]][i-1];
		}
		for(auto nxt:tree[now]){
			//cout<<now<<","<<nxt<<endl;
			dep[nxt] = dep[now]+1;
			par[nxt][0] = now;
			dfs(nxt);
		}
		return;
	}

	void GO(){
		dsu.init(N-1);
		for(int i = N;i<mxn;i++)dsu.dsu[i] = i,dsu.sz[i] = 1;
		for(int i = 0;i<N;i++)val[i].sc = 1;
		int pt = N-1;
		for(int i = 0;i<edges.size();i++){
			auto [a,b] = edges[i].sc;
			int ra = dsu.root(a),rb = dsu.root(b);
			int w = edges[i].fs;
			pt++;
			val[pt].fs = w;
			tree[pt].push_back(dsu.head[ra]);
			if(ra != rb)tree[pt].push_back(dsu.head[rb]);
			dsu.onion(a,b);
			dsu.head[dsu.root(a)] = pt;
			//cout<<pt<<' '<<dsu.root(a)<<':'<<dsu.chn[dsu.root(a)]<<endl;
			val[pt].sc = dsu.chn[dsu.root(a)];
		}
		rt = pt;
		par[rt][0] = rt;
		//for(int i = 0;i<=rt;i++)cout<<i<<":"<<val[i].sc<<endl;
		dfs(rt);
		return;
	}
}

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());
	INIT::GO();
}

int getans(int s,int t){
	if(dep[s]<dep[t])swap(s,t);
	int d = dep[s]-dep[t];
	for(int i = 19;i>=0;i--){
		if(d&(1<<i))s = par[s][i];
	}
	for(int i = 19;i>=0;i--){
		if(par[s][i] != par[t][i])s = par[s][i],t = par[t][i];
	}
	if(s != t)s = t = par[s][0];
	for(int i = 19;i>=0;i--){
		if(dp[s][i])s = par[s][i];
	}
	if(val[s].sc)s = par[s][0];
	if(val[s].sc)return -1;
	else return val[s].fs;
}

int getMinimumFuelCapacity(int s, int t) {
	return getans(s,t);
}

Compilation message (stderr)

swap.cpp: In function 'void INIT::GO()':
swap.cpp:104:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |   for(int i = 0;i<edges.size();i++){
      |                 ~^~~~~~~~~~~~~

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