Submission #1137401

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137401		Saul0906	Thousands Islands (IOI22_islands)	C++20	19.25 / 100	135 ms	49808 KiB

islands

#include "islands.h"
#include <bits/stdc++.h>
#define rep(a,b,c) for(ll a=b; a<c; a++)
#define repr(a,b,c) for(ll a=b-1; a>c-1; a--)
#define repa(a,b) for(auto a:b)
#define ll long long
#define pll pair<ll, ll>
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
#define mid ((l+r)>>1)
#define ppb pop_back
#define pf push_front
#define all(a) a.begin(),a.end()

using namespace std;
using vi = vector<int>;
template<typename T>
using vec = vector<T>;

const int N=2e5+5;

struct kosaraju{
	vi order, scc;
	vec<pii> dag;
	vec<vi> adj;
	vec<bool> vis;
	void dfs(int u){
		vis[u]=true;
		repa(v,adj[u]) if(!vis[v]) dfs(v);
		order.pb(u);
	}
	kosaraju(int n, vec<pii> edges){
		scc.resize(n+1);
		vis.resize(n+1,0);
		adj.resize(n+1);
		repa(e,edges) adj[e.fi].pb(e.se);
		dfs(0);
		fill(all(vis),0);
		rep(i,0,n+1) scc[i]=i;
		repa(e,order){
			queue<int> q;
			q.push(e);
			scc[e]=scc[e];
			vis[e]=true;
			while(q.size()){
				int u=q.front();
				q.pop();
				repa(v,adj[u]){
					if(vis[v]) continue;
					vis[v]=true;
					scc[v]=scc[u];
					q.push(v);
				}
			}
		}
		repa(e,edges) if(scc[e.fi]!=scc[e.se]) dag.pb({scc[e.fi],scc[e.se]});
	}
};

struct component{
	int n, m;
	vi nodes, path, dck;
	set<int> r, r2;
	vec<vi> edges;
	vec<vec<vi>> adj, adj2;
	map<int,int> mp, mp2;
	bool ans=false;
	vec<bool> vis;
	void solve(){
		n=nodes.size();
		m=edges.size();
		adj.resize(n);
		adj2.resize(n);
		vis.resize(n,0);
		dck.resize(m);
		rep(i,0,n) mp[nodes[i]]=i;
		rep(i,0,m) mp2[edges[i][2]]=i;
		repa(e,edges){
			adj[mp[e[0]]].pb({mp[e[1]]});
			adj2[mp[e[0]]].pb({mp[e[1]]});
		}
		repa(e,r) r2.insert(mp[e]);
		repa(e,nodes) if(e==0) r2.insert(mp[e]);
		rep(u,0,n){
			int cnt=0;
			repa(v,adj[u]) if(adj2[u].size()>2 || v!=adj2[u][0] || r2.count(u)) cnt++;
			if(cnt>1) ans=true;
		}
	}
};

std::variant<bool, std::vector<int>> find_journey(
	int N, int M, std::vector<int> U, std::vector<int> V) {
	vec<pii> edges;
	rep(i,0,M) edges.pb({U[i],V[i]});
	kosaraju find_scc(N,edges);
	component comp[N];
	int in[N]{}, dp[N]{}, sz[N]{}, u, v;
	queue<int> q;
	vi adj[N];
	bool ans=false;
	vi scc=find_scc.scc;
	repa(e,find_scc.dag) adj[e.fi].pb(e.se), in[e.se]++;
	rep(i,0,N) if(scc[i]==i && !in[i]) q.push(i);
	rep(i,0,N) sz[scc[i]]++, comp[scc[i]].nodes.pb(i);
	rep(i,0,M) if(scc[U[i]]==scc[V[i]]) comp[scc[U[i]]].edges.pb({U[i],V[i],i});
	dp[scc[0]]=1;
	while(q.size()){
		u=q.front();
		q.pop();
		if(dp[u]==2 && sz[u]>1) ans=true;
		repa(v,adj[u]){
			in[v]--;
			dp[v]=min(2,dp[u]+dp[v]);
			if(!in[v]) q.push(v);
		}
	}
	rep(i,0,M) if(scc[U[i]]!=scc[V[i]] && dp[scc[U[i]]]) comp[scc[V[i]]].r.insert(V[i]);
	rep(i,0,N) if(scc[i]==i && dp[i]) comp[i].solve(), ans|=(comp[i].ans);
	return ans;
}

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:108:81: warning: narrowing conversion of 'i' from 'long long int' to 'int' [-Wnarrowing]
  108 |         rep(i,0,M) if(scc[U[i]]==scc[V[i]]) comp[scc[U[i]]].edges.pb({U[i],V[i],i});
      |                                                                                 ^
islands.cpp:108:81: warning: narrowing conversion of 'i' from 'long long int' to 'int' [-Wnarrowing]

• Subtask 1: 1.75 / 5
• Subtask 2: 1.75 / 5
• Subtask 3: 7.35 / 21
• Subtask 4: 8.4 / 24
• Subtask 5: 0 / 45