Submission #628390

#	Time	Username	Problem	Language	Result	Execution time	Memory
628390		haojiandan	Thousands Islands (IOI22_islands)	C++17	100 / 100	121 ms	20108 KiB

islands

#include "islands.h"
#include <bits/stdc++.h>
using namespace std;
#define MP make_pair
const int maxn=(1e5)+10;
int n,m; vector<int> bk[maxn];
int out[maxn],q[maxn],hd,tl;
bool del[maxn];
vector<int> ans,vec,res;
vector<pair<int,int> > g[maxn];
int to[maxn];
int d[maxn],t1,e[maxn],t2;
int pos[maxn],vis[maxn],To[maxn];
int D[maxn],E[maxn];
int at[maxn*2];

variant<bool,vector<int> > find_journey(int _n,int _m,vector<int> U,vector<int> V) {
   	n=_n,m=_m;
   	for (int i=0;i<m;i++) bk[V[i]].push_back(U[i]),g[U[i]].push_back(MP(V[i],i)),out[U[i]]++;
   	int x=0;
   	for (int i=0;i<n;i++) if (!out[i]) q[++tl]=i,del[i]=1; hd=1;
   	while (hd<=tl||out[x]==1) {
	   	while (hd<=tl) {
	   		int x=q[hd]; hd++;
	   		for (int &y : bk[x]) { out[y]--; if (!out[y]) q[++tl]=y,del[y]=1; }
	   	}
	   	while (out[x]==1) {
	   		del[x]=1;
	   		for (int &y : bk[x]) { out[y]--; if (!out[y]&&!del[y]) q[++tl]=y,del[y]=1; }
	   		bool fd=0;
	   		for (auto [y,id] : g[x]) if (!del[y]) { fd=1; vec.push_back(id); x=y; break; }
	   	//	printf("x=%d\n",x);
	   		if (!fd) return false;
	   	}
	  // 	printf("x=%d\n",x);
	}
	if (out[x]<2) return false;
   	for (int i=0;i<n;i++) if (!del[i]) {
   		for (auto [j,id] : g[i]) if (!del[j]) to[i]=j,To[i]=id;
   	}
   	int a=-1,b=-1;
   	for (auto [y,id] : g[x]) if (!del[y]) {
   		if (a==-1) a=y,D[1]=id; else b=y,E[1]=id;
   	}
  // 	cerr<<x<<" "<<a<<" "<<b<<endl;
	int l,r;
	int y=a; vis[x]=1; d[t1=1]=x;
	while (!vis[y]) vis[y]=1,d[++t1]=y,D[t1]=To[y],y=to[y];
	for (int i=1;i<=t1;i++) if (y==d[i]) l=i;
	memset(vis,0,sizeof(vis));
	y=b; vis[x]=1; e[t2=1]=x;
	while (!vis[y]) vis[y]=1,e[++t2]=y,E[t2]=To[y],y=to[y];
	for (int i=1;i<=t2;i++) if (y==e[i]) r=i;
	
	for (int i=1;i<=t1;i++) pos[d[i]]=i;
	int fd=0;
	for (int i=2;i<=t2;i++) if (pos[e[i]]) { fd=i; break; }
	//printf("fd=%d\n",fd);
	//for (int i=1;i<=t1;i++) printf("%d ",d[i]); puts("");
	//for (int i=1;i<=t2;i++) printf("%d ",e[i]); puts("");
	//printf("l=%d,fd=%d\n",l,fd);
	//puts("OK");
	if (fd) {
		if (pos[e[fd]]<l) {
			for (int i=1;i<=t1;i++) ans.push_back(D[i]);
			for (int i=l-1;i>=1;i--) ans.push_back(D[i]);
			for (int i=1;i<fd;i++) ans.push_back(E[i]);
			for (int i=pos[e[fd]];i<l;i++) ans.push_back(D[i]);
			for (int i=t1;i>=pos[e[fd]];i--) ans.push_back(D[i]);
			for (int i=fd-1;i>=1;i--) ans.push_back(E[i]);
		} else {
			for (int i=1;i<=t1;i++) ans.push_back(D[i]);
			for (int i=l-1;i>=1;i--) ans.push_back(D[i]);
			for (int i=1;i<fd;i++) ans.push_back(E[i]);
			for (int i=pos[e[fd]]-1;i>=l;i--) ans.push_back(D[i]);
			for (int i=t1;i>=pos[e[fd]];i--) ans.push_back(D[i]);
			for (int i=fd-1;i>=1;i--) ans.push_back(E[i]);
		}
	} else {
		for (int i=1;i<=t1;i++) ans.push_back(D[i]);
		for (int i=l-1;i>=1;i--) ans.push_back(D[i]);
		for (int i=1;i<=t2;i++) ans.push_back(E[i]);
		for (int i=r-1;i>=1;i--) ans.push_back(E[i]);
		
		for (int i=1;i<l;i++) ans.push_back(D[i]);
		for (int i=t1;i>=1;i--) ans.push_back(D[i]);
		for (int i=1;i<r;i++) ans.push_back(E[i]);
		for (int i=t2;i>=1;i--) ans.push_back(E[i]);
	}
	for (int &x : vec) res.push_back(x);
	for (int &x : ans) res.push_back(x);
	reverse(vec.begin(),vec.end());
	for (int &x : vec) res.push_back(x);
/*	for (int &x : res) printf("%d ",x); puts("");
int now=0;
for (int &x : res) {
	printf("%d %d %d\n",x,U[x],V[x]);
	if (at[x]) assert(now==V[x]); else assert(now==U[x]);
	at[x]^=1,now=(V[x]^U[x]^now);
}
assert(now==0);
for (int i=0;i<m;i++) assert(!at[i]);*/

	return res;
}

Compilation message (stderr)

islands.cpp: In function 'std::variant<bool, std::vector<int, std::allocator<int> > > find_journey(int, int, std::vector<int>, std::vector<int>)':
islands.cpp:21:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   21 |     for (int i=0;i<n;i++) if (!out[i]) q[++tl]=i,del[i]=1; hd=1;
      |     ^~~
islands.cpp:21:60: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   21 |     for (int i=0;i<n;i++) if (!out[i]) q[++tl]=i,del[i]=1; hd=1;
      |                                                            ^~
islands.cpp:46:8: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
   46 |  int l,r;
      |        ^

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