Submission #636219

#	Time	Username	Problem	Language	Result	Execution time	Memory
636219		kig9981	Thousands Islands (IOI22_islands)	C++17	100 / 100	500 ms	70020 KiB

islands

#include "islands.h"
#include <variant>
#include <bits/stdc++.h>

#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif

using namespace std;

const int SZ=1<<17;
vector<pair<int,int>> adj[100000];
vector<int> tadj[100000], radj[100000], S, Q[100000], FQ[100000], CQ[100000], ans;
set<pair<int,int>> FE;
map<pair<int,int>,int> E, SE;
int node_cnt, W[100000], num[100000], hld[100000], R[100000], parent[100000], depth[100000], D[100000];
bool chk[100000], DE[100000];
pair<int,int> tree[2*SZ], lazy[2*SZ];

void solution1(int a, int b, int e);
void solution2(int a, int b, pair<int,int> c);
void solution3(pair<int,int> a, pair<int,int> b);
void solution4(int a, int b);

pair<int,int> get_max(pair<int,int> a, pair<int,int> b)
{
	if(a==make_pair(-1,-1)) return b;
	if(b==make_pair(-1,-1)) return a;
	return depth[a.first]>depth[b.first] ? a:b;
}

void lazy_propagation(int bit, int s, int e)
{
	if(lazy[bit]==make_pair(-1,-1)) return;
	tree[bit]=get_max(tree[bit],lazy[bit]);
	if(s<e) {
		lazy[2*bit]=get_max(lazy[2*bit],lazy[bit]);
		lazy[2*bit+1]=get_max(lazy[2*bit+1],lazy[bit]);
	}
	lazy[bit]={-1,-1};
}

void update(int n1, int n2, pair<int,int> v, int bit=1, int s=0, int e=SZ-1)
{
	int m=(s+e)>>1;
	lazy_propagation(bit,s,e);
	if(n2<n1 || n2<s || e<n1) return;
	if(n1<=s && e<=n2) {
		lazy[bit]=v;
		lazy_propagation(bit,s,e);
		return;
	}
	update(n1,n2,v,2*bit,s,m);
	update(n1,n2,v,2*bit+1,m+1,e);
	tree[bit]=get_max(tree[2*bit],tree[2*bit+1]);
}

pair<int,int> query(int n1, int n2, int bit=1, int s=0, int e=SZ-1)
{
	int m=(s+e)>>1;
	lazy_propagation(bit,s,e);
	if(n2<n1 || n2<s || e<n1) return {-1,-1};
	if(n1<=s && e<=n2) return tree[bit];
	return get_max(query(n1,n2,2*bit,s,m),query(n1,n2,2*bit+1,m+1,e));
}

void dfs(int c)
{
	S.push_back(c);
	W[c]=chk[c]=true;
	for(auto[n,e]: adj[c]) {
		if(E.count({c,n})) SE[{c,n}]=e;
		else E[{c,n}]=e;
		if(W[n]==0) {
			tadj[c].push_back(n);
			parent[n]=c;
			D[n]=depth[n]=depth[c]+1;
			dfs(n);
			W[c]+=W[n];
		}
		else if(chk[n]) Q[S[depth[n]+1]].push_back(c);
		else if(FE.find({c,n})!=FE.end()) FQ[c].push_back(n);
		else CQ[c].push_back(n);
	}
	for(auto n: radj[c]) if(chk[n]) FE.emplace(n,c);
	chk[c]=false;
	S.pop_back();
}

void dfs2(int c)
{
	int mx=-1;
	num[c]=node_cnt++;
	S.push_back(c);
	for(auto n: Q[c]) {
		if(D[c]==D[parent[c]]) {
			solution1(parent[c],n,SE[{parent[c],c}]);
			return;
		}
		if(DE[parent[c]]) {
			solution4(parent[c],n);
			return;
		}
		auto q=query(num[c],num[c]+W[c]-1);
		if(q!=make_pair(-1,-1)) {
			solution3(q,make_pair(parent[c],n));
			return;
		}
		update(0,num[c]-1,make_pair(parent[c],n));
		update(num[c]+W[c],SZ-1,make_pair(parent[c],n));
	}
	for(auto n: tadj[c]) if(mx==-1 || W[mx]<W[n]) mx=n;
	if(mx==-1) {
		S.pop_back();
		R[c]=node_cnt-1;
		return;
	}
	hld[mx]=hld[c];
	DE[mx]=DE[c];
	if(SE.count({c,mx})) {
		D[mx]=D[c];
		DE[mx]=true;
	}
	dfs2(mx);
	if(ans.size()) return;
	for(auto n: tadj[c]) if(mx!=n) {
		DE[n]=DE[c];
		if(SE.count({c,n})) {
			D[n]=D[c];
			DE[n]=true;
		}
		dfs2(hld[n]=n);
		if(ans.size()) return;
	}
	R[c]=node_cnt-1;
	S.pop_back();
}

void query(int a, int b, pair<int,int> v)
{
	while(hld[a]!=hld[b]) {
		update(num[hld[b]],num[b],v);
		b=parent[hld[b]];
	}
	update(num[a],num[b],v);
}

void dfs3(int c)
{
	for(auto n: tadj[c]) if(parent[n]==c) {
		dfs3(n);
		if(ans.size()) return;
	}
	for(auto n: Q[c]) query(0,n,make_pair(parent[c],n));
	for(auto n: FQ[c]) {
		auto q=query(num[n],num[n]);
		if(q!=make_pair(-1,-1) && depth[c]<=depth[q.first]) {
			solution2(c,n,q);
			return;
		}
	}
	for(auto n: CQ[c]) {
		auto q=query(num[n],num[n]);
		if(q!=make_pair(-1,-1)) {
			solution2(c,n,q);
			return;
		}
	}
}

variant<bool,vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V)
{
	ans.clear(); S.clear(); E.clear(); SE.clear();
	for(int i=0;i<N;i++) {
		adj[i].clear(); Q[i].clear(); FQ[i].clear(); CQ[i].clear();
		tadj[i].clear(); radj[i].clear();
		W[i]=chk[i]=DE[i]=false;
	}
	for(int i=2*SZ;--i;) tree[i]=lazy[i]={-1,-1};
	for(int i=0;i<M;i++) {
		adj[U[i]].emplace_back(V[i],i);
		radj[V[i]].push_back(U[i]);
	}
	dfs(0); dfs2(0);
	if(ans.empty()) {
		for(int i=2*SZ;--i;) tree[i]=lazy[i]={-1,-1};
		dfs3(0);
		if(ans.size()) return ans;
		return false;
	}
	return ans;
}

void solution1(int a, int b, int e)
{
	vector<int> ZA, A, temp;
	A.push_back(a); A.push_back(b); ZA.push_back(a);
	for(int i=a;i;i=parent[i]) ZA.push_back(parent[i]);
	reverse(ZA.begin(),ZA.end());
	swap(temp,ZA); ZA.clear();
	for(int i=1;i<temp.size();i++) ZA.push_back(E[{temp[i-1],temp[i]}]);
	for(int i=b;i!=a;i=parent[i]) A.push_back(parent[i]);
	reverse(A.begin(),A.end());
	swap(temp,A); A.clear();
	for(int i=1;i<temp.size();i++) A.push_back(E[{temp[i-1],temp[i]}]);
	for(auto a: ZA) ans.push_back(a);
	for(auto a: A) ans.push_back(a);
	ans.push_back(e); ans.push_back(A[0]); A[0]=e;
	reverse(A.begin(),A.end()); reverse(ZA.begin(),ZA.end());
	for(auto a: A) ans.push_back(a);
	for(auto a: ZA) ans.push_back(a);
}

void solution2(int a, int b, pair<int,int> c)
{
	vector<int> L, LA, LB, A, B, temp;
	int l, x=a, y=c.first;
	if(depth[x]<depth[y]) swap(x,y);
	while(depth[x]!=depth[y]) x=parent[x];
	while(x!=y) {
		x=parent[x];
		y=parent[y];
	}
	L.push_back(l=x);
	for(int i=l;i;i=parent[i]) L.push_back(parent[i]);
	reverse(L.begin(),L.end());
	swap(temp,L); L.clear();
	for(int i=1;i<temp.size();i++) L.push_back(E[{temp[i-1],temp[i]}]);
	if(depth[c.first]<=depth[b]) {
		LA.push_back(x=c.first); LB.push_back(b); LB.push_back(a);
		for(int i=x;i!=l;i=parent[i]) LA.push_back(parent[i]);
		reverse(LA.begin(),LA.end());
		swap(temp,LA); LA.clear();
		for(int i=1;i<temp.size();i++) LA.push_back(E[{temp[i-1],temp[i]}]);
		for(int i=a;i!=l;i=parent[i]) LB.push_back(parent[i]);
		reverse(LB.begin(),LB.end());
		swap(temp,LB); LB.clear();
		for(int i=1;i<temp.size();i++) LB.push_back(E[{temp[i-1],temp[i]}]);
		A.push_back(x); A.push_back(c.second);
		for(int i=c.second;i!=x;i=parent[i]) A.push_back(parent[i]);
		reverse(A.begin(),A.end());
		for(int i=1;i<A.size();i++) if(A[i]==b) {
			for(int j=i;j<A.size();j++) B.push_back(A[j]);
			for(int j=1;j<=i;j++) B.push_back(A[j]);
			break;
		}
		swap(temp,A); A.clear();
		for(int i=1;i<temp.size();i++) A.push_back(E[{temp[i-1],temp[i]}]);
		swap(temp,B); B.clear();
		for(int i=1;i<temp.size();i++) B.push_back(E[{temp[i-1],temp[i]}]);
		for(auto a: L) ans.push_back(a);
		for(auto a: LA) ans.push_back(a);
		for(auto a: A) ans.push_back(a);
		reverse(LA.begin(),LA.end());
		for(auto a: LA) ans.push_back(a);
		for(auto a: LB) ans.push_back(a);
		reverse(B.begin(),B.end());
		for(auto a: B) ans.push_back(a);
		reverse(LB.begin(),LB.end());
		for(auto a: LB) ans.push_back(a);
		reverse(L.begin(),L.end());
		for(auto a: L) ans.push_back(a);
	}
	else {
		bool r=false;
		LA.push_back(x=c.first); LB.push_back(b); LB.push_back(a);
		for(int i=a;i!=l;i=parent[i]) LB.push_back(parent[i]);
		reverse(LB.begin(),LB.end());
		swap(temp,LB); LB.clear();
		for(int i=1;i<temp.size();i++) LB.push_back(E[{temp[i-1],temp[i]}]);
		for(int i=x;i!=l;i=parent[i]) LA.push_back(parent[i]);
		reverse(LA.begin(),LA.end());
		swap(temp,LA); LA.clear();
		for(int i=1;i<temp.size();i++) {
			LA.push_back(E[{temp[i-1],temp[i]}]);
			if(r) LB.push_back(E[{temp[i-1],temp[i]}]);
			if(temp[i]==b) r=true;
		}
		A.push_back(x); A.push_back(c.second);
		for(int i=c.second;i!=x;i=parent[i]) A.push_back(parent[i]);
		reverse(A.begin(),A.end());
		swap(temp,A); A.clear();
		for(int i=1;i<temp.size();i++) A.push_back(E[{temp[i-1],temp[i]}]);
		for(auto a: L) ans.push_back(a);
		for(auto a: LA) ans.push_back(a);
		for(auto a: A) ans.push_back(a);
		reverse(LA.begin(),LA.end());
		for(auto a: LA) ans.push_back(a);
		for(auto a: LB) ans.push_back(a);
		reverse(A.begin(),A.end());
		for(auto a: A) ans.push_back(a);
		reverse(LB.begin(),LB.end());
		for(auto a: LB) ans.push_back(a);
		reverse(L.begin(),L.end());
		for(auto a: L) ans.push_back(a);
	}
}

void solution3(pair<int,int> a, pair<int,int> b)
{
	vector<int> L, LA, LB, A, B, temp;
	int l, x=a.first, y=b.first;
	if(depth[x]<depth[y]) swap(x,y);
	while(depth[x]!=depth[y]) x=parent[x];
	while(x!=y) {
		x=parent[x];
		y=parent[y];
	}
	L.push_back(l=x);
	for(int i=l;i;i=parent[i]) L.push_back(parent[i]);
	reverse(L.begin(),L.end());
	swap(temp,L); L.clear();
	for(int i=1;i<temp.size();i++) L.push_back(E[{temp[i-1],temp[i]}]);
	A.push_back(x=a.first); B.push_back(y=b.first);
	A.push_back(a.second); B.push_back(b.second);
	LA.push_back(x); LB.push_back(y);
	for(int i=x;i!=l;i=parent[i]) LA.push_back(parent[i]);
	for(int i=y;i!=l;i=parent[i]) LB.push_back(parent[i]);
	reverse(LA.begin(),LA.end()); reverse(LB.begin(),LB.end());
	swap(temp,LA); LA.clear();
	for(int i=1;i<temp.size();i++) LA.push_back(E[{temp[i-1],temp[i]}]);
	swap(temp,LB); LB.clear();
	for(int i=1;i<temp.size();i++) LB.push_back(E[{temp[i-1],temp[i]}]);
	for(int i=a.second;i!=x;i=parent[i]) A.push_back(parent[i]);
	for(int i=b.second;i!=y;i=parent[i]) B.push_back(parent[i]);
	reverse(A.begin(),A.end()); reverse(B.begin(),B.end());
	swap(temp,A); A.clear();
	for(int i=1;i<temp.size();i++) A.push_back(E[{temp[i-1],temp[i]}]);
	swap(temp,B); B.clear();
	for(int i=1;i<temp.size();i++) B.push_back(E[{temp[i-1],temp[i]}]);
	for(auto a: L) ans.push_back(a);
	for(auto a: LA) ans.push_back(a);
	for(auto a: A) ans.push_back(a);
	reverse(LA.begin(),LA.end());
	for(auto a: LA) ans.push_back(a);
	for(auto a: LB) ans.push_back(a);
	for(auto a: B) ans.push_back(a);
	reverse(LB.begin(),LB.end());
	for(auto a: LB) ans.push_back(a);
	reverse(LA.begin(),LA.end());
	for(auto a: LA) ans.push_back(a);
	reverse(A.begin(),A.end());
	for(auto a: A) ans.push_back(a);
	reverse(LA.begin(),LA.end());
	for(auto a: LA) ans.push_back(a);
	reverse(LB.begin(),LB.end());
	for(auto a: LB) ans.push_back(a);
	reverse(B.begin(),B.end());
	for(auto a: B) ans.push_back(a);
	reverse(LB.begin(),LB.end());
	for(auto a: LB) ans.push_back(a);
	reverse(L.begin(),L.end());
	for(auto a: L) ans.push_back(a);
}

void solution4(int a, int b)
{
	vector<int> ZA, A, temp;
	int r=-1, rp=-1;
	A.push_back(a); A.push_back(b); ZA.push_back(a);
	for(int i=a;i;i=parent[i]) ZA.push_back(parent[i]);
	reverse(ZA.begin(),ZA.end());
	swap(temp,ZA); ZA.clear();
	for(int i=1;i<temp.size();i++) {
		ZA.push_back(E[{temp[i-1],temp[i]}]);
		if(r==-1 && SE.count({temp[i-1],temp[i]})) {
			r=SE[{temp[i-1],temp[i]}];
			rp=ZA.size()-1;
		}
	}
	for(int i=b;i!=a;i=parent[i]) A.push_back(parent[i]);
	reverse(A.begin(),A.end());
	swap(temp,A); A.clear();
	for(int i=1;i<temp.size();i++) A.push_back(E[{temp[i-1],temp[i]}]);
	for(auto a: ZA) ans.push_back(a);
	for(auto a: A) ans.push_back(a);
	for(int i=ZA.size();--i>=rp;) ans.push_back(ZA[i]);
	ZA[rp]=r;
	for(int i=rp;i<ZA.size();i++) ans.push_back(ZA[i]);
	reverse(A.begin(),A.end()); reverse(ZA.begin(),ZA.end());
	for(auto a: A) ans.push_back(a);
	for(auto a: ZA) ans.push_back(a);
}

Compilation message (stderr)

islands.cpp: In function 'void solution1(int, int, int)':
islands.cpp:205:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  205 |  for(int i=1;i<temp.size();i++) ZA.push_back(E[{temp[i-1],temp[i]}]);
      |              ~^~~~~~~~~~~~
islands.cpp:209:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  209 |  for(int i=1;i<temp.size();i++) A.push_back(E[{temp[i-1],temp[i]}]);
      |              ~^~~~~~~~~~~~
islands.cpp: In function 'void solution2(int, int, std::pair<int, int>)':
islands.cpp:232:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  232 |  for(int i=1;i<temp.size();i++) L.push_back(E[{temp[i-1],temp[i]}]);
      |              ~^~~~~~~~~~~~
islands.cpp:238:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  238 |   for(int i=1;i<temp.size();i++) LA.push_back(E[{temp[i-1],temp[i]}]);
      |               ~^~~~~~~~~~~~
islands.cpp:242:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  242 |   for(int i=1;i<temp.size();i++) LB.push_back(E[{temp[i-1],temp[i]}]);
      |               ~^~~~~~~~~~~~
islands.cpp:246:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  246 |   for(int i=1;i<A.size();i++) if(A[i]==b) {
      |               ~^~~~~~~~~
islands.cpp:247:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  247 |    for(int j=i;j<A.size();j++) B.push_back(A[j]);
      |                ~^~~~~~~~~
islands.cpp:252:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  252 |   for(int i=1;i<temp.size();i++) A.push_back(E[{temp[i-1],temp[i]}]);
      |               ~^~~~~~~~~~~~
islands.cpp:254:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  254 |   for(int i=1;i<temp.size();i++) B.push_back(E[{temp[i-1],temp[i]}]);
      |               ~^~~~~~~~~~~~
islands.cpp:274:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  274 |   for(int i=1;i<temp.size();i++) LB.push_back(E[{temp[i-1],temp[i]}]);
      |               ~^~~~~~~~~~~~
islands.cpp:278:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  278 |   for(int i=1;i<temp.size();i++) {
      |               ~^~~~~~~~~~~~
islands.cpp:287:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  287 |   for(int i=1;i<temp.size();i++) A.push_back(E[{temp[i-1],temp[i]}]);
      |               ~^~~~~~~~~~~~
islands.cpp: In function 'void solution3(std::pair<int, int>, std::pair<int, int>)':
islands.cpp:317:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  317 |  for(int i=1;i<temp.size();i++) L.push_back(E[{temp[i-1],temp[i]}]);
      |              ~^~~~~~~~~~~~
islands.cpp:325:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  325 |  for(int i=1;i<temp.size();i++) LA.push_back(E[{temp[i-1],temp[i]}]);
      |              ~^~~~~~~~~~~~
islands.cpp:327:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  327 |  for(int i=1;i<temp.size();i++) LB.push_back(E[{temp[i-1],temp[i]}]);
      |              ~^~~~~~~~~~~~
islands.cpp:332:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  332 |  for(int i=1;i<temp.size();i++) A.push_back(E[{temp[i-1],temp[i]}]);
      |              ~^~~~~~~~~~~~
islands.cpp:334:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  334 |  for(int i=1;i<temp.size();i++) B.push_back(E[{temp[i-1],temp[i]}]);
      |              ~^~~~~~~~~~~~
islands.cpp: In function 'void solution4(int, int)':
islands.cpp:368:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  368 |  for(int i=1;i<temp.size();i++) {
      |              ~^~~~~~~~~~~~
islands.cpp:378:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  378 |  for(int i=1;i<temp.size();i++) A.push_back(E[{temp[i-1],temp[i]}]);
      |              ~^~~~~~~~~~~~
islands.cpp:383:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  383 |  for(int i=rp;i<ZA.size();i++) ans.push_back(ZA[i]);
      |               ~^~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 21 / 21
• Subtask 4: 24 / 24
• Subtask 5: 45 / 45