Submission #410724

#	Time	Username	Problem	Language	Result	Execution time	Memory
410724		songc	Swapping Cities (APIO20_swap)	C++14	17 / 100	129 ms	38976 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define lb lower_bound
#define MOD 1000000007
#define INF (1ll<<62)
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;

struct Edge{int u, v, w;} E[202020];

int M, D[101010];
vector<pii> P[101010], C[101010];

int Pf(int u, int t){return P[u][lb(P[u].begin(), P[u].end(), pii(t+1, 0))-P[u].begin()-1].se;}
int Cf(int u, int t){return C[u][lb(C[u].begin(), C[u].end(), pii(t+1, 0))-C[u].begin()-1].se;}

int rt(int u, int t){
	if (Pf(u, t) < 0) return u;
	return rt(Pf(u, t), t);
}

void init(int N, int _M, vector<int> U, vector<int> V, vector<int> W) {
	M = _M;
	E[0].w = -1;
	for (int i=0; i<M; i++) E[i+1] = (Edge){U[i]+1, V[i]+1, W[i]};
	sort(E+1, E+M+1, [](Edge a, Edge b){return a.w < b.w;});
	for (int i=1; i<=N; i++) P[i].pb(pii(0, -i)), C[i].pb(pii(0, 0));
	for (int i=1; i<=M; i++){
		int ru = rt(E[i].u, i), rv = rt(E[i].v, i);
		if (ru != rv){
			if (Pf(ru, i) < Pf(rv, i)) swap(ru, rv);
			P[rv].pb(pii(i, Pf(ru, i)+Pf(rv, i)));
			P[ru].pb(pii(i, rv));
			if (Cf(ru, i) || Cf(rv, i)) C[rv].pb(pii(i, 1));
		}
		else C[rv].pb(pii(i, 1));
		D[E[i].u]++, D[E[i].v]++;
		if (D[E[i].u] > 2 || D[E[i].v] > 2) C[rv].pb(pii(i, 1));
	}
}

int getMinimumFuelCapacity(int X, int Y) {
	X++, Y++;
	int ans=0, lo=1, hi=M;
	while (lo<=hi){
		int m=lo+hi>>1;
		if (rt(X, m) == rt(Y, m) && Cf(rt(X, m), m)) ans=m, hi=m-1;
		else lo=m+1;
	}
	return E[ans].w;
}

Compilation message (stderr)

swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:50:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   50 |   int m=lo+hi>>1;
      |         ~~^~~

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