Submission #398139

#	Time	Username	Problem	Language	Result	Execution time	Memory
398139		ZikXewen	Swapping Cities (APIO20_swap)	C++17	100 / 100	681 ms	57372 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
typedef tuple<int, int, int> ii;
const int X = 1e5 + 5, R = 1e9 + 5, L = 20;
int N, M, CT;
vector<ii> ed;
struct node{
	int nl, e1, e2, id, dp;
	node *pa[L], *ppa;
	node* fd(){return ppa? ppa = ppa -> fd() : this;}
	void ste(int u, int v){e1 = u, e2 = v;}
	void stp(node *u){pa[0] = ppa = u;}
	node(int u) : id(u), nl(), e1(u), e2(u), pa(), ppa(), dp() {}
} *tr[X << 1];
void un(int u, int v, int po){
	node *pu = tr[u] -> fd(), *pv = tr[v] -> fd();
	if(pu == pv){
		if(!pu -> nl) pu -> nl = po;
		return;
	}
	node *nw = tr[CT++] = new node(CT);
	pu -> stp(nw), pv -> stp(nw);
	if(pv -> nl or pu -> nl) return nw -> nl = po, void();
	if(u == pu -> e1 and v == pv -> e1) return nw -> ste(pu -> e2, pv -> e2), void();
	if(u == pu -> e1 and v == pv -> e2) return nw -> ste(pu -> e2, pv -> e1), void();
	if(u == pu -> e2 and v == pv -> e1) return nw -> ste(pu -> e1, pv -> e2), void();
	if(u == pu -> e2 and v == pv -> e2) return nw -> ste(pu -> e1, pv -> e1), void();
	nw -> nl = po;
}
void init(int _N, int _M, vector<int> U, vector<int> V, vector<int> W) {
	N = _N; M = _M;
	for(int i = 0; i < N; ++i) tr[CT++] = new node(i);
	for(int i = 0; i < M; ++i) ed.emplace_back(U[i], V[i], W[i]);
	sort(ed.begin(), ed.end(), [=](ii u, ii v){return get<2>(u) < get<2>(v);});
	for(auto [u, v, w]: ed) un(u, v, w);
	tr[CT - 1] -> dp = 1;
	for(int i = 1; i < L; ++i) for(int j = 0; j < CT; ++j) if(tr[j] -> pa[i - 1]) {
		tr[j] -> pa[i] = tr[j] -> pa[i - 1] -> pa[i - 1];
		if(tr[j] -> pa[i - 1] -> dp) tr[j] -> dp = tr[j] -> pa[i - 1] -> dp + (1 << (i - 1));
	}
}
int getMinimumFuelCapacity(int u, int v) {
	node *pu = tr[u], *pv = tr[v];
	if(pu -> dp < pv -> dp) swap(pu, pv);
	for(int i = L - 1; i >= 0; --i) if(pu -> pa[i] and pu -> pa[i] -> dp >= pv -> dp) pu = pu -> pa[i];
	if(pu != pv){
		for(int i = L - 1; i >= 0; --i) if(pu -> pa[i] != pv -> pa[i]) pu = pu -> pa[i], pv = pv -> pa[i];
		pu = pu -> pa[0];
	}
	if(pu -> nl) return pu -> nl;
	for(int i = L - 1; i >= 0; --i) if(pu -> pa[i] and !pu -> pa[i] -> nl) pu = pu -> pa[i];
	return pu -> pa[0]? pu -> pa[0] -> nl : -1;
}

Compilation message (stderr)

swap.cpp: In constructor 'node::node(int)':
swap.cpp:9:18: warning: 'node::id' will be initialized after [-Wreorder]
    9 |  int nl, e1, e2, id, dp;
      |                  ^~
swap.cpp:9:6: warning:   'int node::nl' [-Wreorder]
    9 |  int nl, e1, e2, id, dp;
      |      ^~
swap.cpp:14:2: warning:   when initialized here [-Wreorder]
   14 |  node(int u) : id(u), nl(), e1(u), e2(u), pa(), ppa(), dp() {}
      |  ^~~~
swap.cpp:10:16: warning: 'node::ppa' will be initialized after [-Wreorder]
   10 |  node *pa[L], *ppa;
      |                ^~~
swap.cpp:9:22: warning:   'int node::dp' [-Wreorder]
    9 |  int nl, e1, e2, id, dp;
      |                      ^~
swap.cpp:14:2: warning:   when initialized here [-Wreorder]
   14 |  node(int u) : id(u), nl(), e1(u), e2(u), pa(), ppa(), dp() {}
      |  ^~~~
swap.cpp: In function 'void un(int, int, int)':
swap.cpp:22:18: warning: operation on 'CT' may be undefined [-Wsequence-point]
   22 |  node *nw = tr[CT++] = new node(CT);
      |                ~~^~

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