Submission #1285877

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285877		justinlgl20	Information (CEOI08_information)	C++20	76 / 100	126 ms	45532 KiB

information

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define F(i,l,r) for(int i=l,i##_end=r;i<i##_end;i++)
#define all(x) (x).begin(), (x).end()
#define pii pair<int, int>
#define f first
#define s second
 
template<template<typename> class Container, typename G>
ostream& operator<<(ostream& os, Container<G> x) {int f=0;os<<'{';for(auto&i:x)os<<(f++ ? ", " : ""),os<<i;os<<"}";return os;}
void _print() {cerr << "]\n";}
template<typename T, typename... V>
void _print(T t, V... v) {cerr << t; if (sizeof...(v)) cerr <<", "; _print(v...);}
#ifdef DEBUG
#define dbg(x...) cerr << "\e[91m"<<__func__<<":"<<__LINE__<<" [" << #x << "] = ["; _print(x); cerr << "\e[39m" << endl;
#else
#define dbg(x...)
#endif

int head[2005];
struct edge{int u,nxt;};
edge e[1000005];
int use[1000005],use2[1000005],in[2005],a[1000005],b[1000005];
vector<int>cur;

int32_t main(){
	cin.tie(0)->sync_with_stdio(false);
	int n,m;cin>>n>>m;
	F(i,0,m){
		int a,b;cin>>a>>b;
		::a[i+1]=a;::b[i+1]=b;
		//if(head[a]==0)head[a]=i+1;
		//else e[head[a]].nxt=i+1;
		e[i+1].u=b;e[i+1].nxt=0;
		e[i+1].nxt=head[a];
		head[a]=i+1;
	}
	// let's find a spanning tree
	vector<int>seen(n+1);
	vector<int>edges;
	vector<int>s(n+1),p(n+1),tin(n+1),tout(n+1);int c=0;
	int cnt=0;
	vector<vector<pii>>above(n+3);
	function<void(int)>build=[&](int u){
		tin[u]=cnt++;
		s[u]=1;
		for(int id=head[u];id!=0;id=e[id].nxt){
			if(!s[e[id].u] and use[id]==0){
				p[e[id].u]=id;
				cur.push_back(id);
				c++;
				use[id]=1;
				build(e[id].u);
			}
		}
		tout[u]=cnt++;
	};
	build(1);
	/*F(i,1,m+1){
		if(tin[a[i]]<=tin[b[i]] and tout[b[i]]<=tout[a[i]] and use[i]==0){
			dbg(b[i],a[i],i);
			above[b[i]].emplace_back(a[i],i);
		}
	}*/
	F(i,1,n+1){
		for(int id=head[i];id;id=e[id].nxt){
			if(tin[i]<=tin[e[id].u] and tout[e[id].u]<=tout[i] and use[id]==0){
				above[e[id].u].emplace_back(i,id);
			}
		}
	}
	dbg(cur);
	function<void(int)>dfs=[&](int u){
		if(seen[u])return;
		seen[u]=1;
		for(int id=head[u];id!=0;id=e[id].nxt){
			if(!seen[e[id].u]){
				if(use[id]==0){
					use[id]=2;
					dbg(id);
					dfs(e[id].u);
				}else if(above[e[id].u].size()){
					// these edges could substitute in our tree
					int from=above[e[id].u].back().f,ed=above[e[id].u].back().s;
					dbg(id,ed,b[ed],b[id],"SWAP");
					use[id]=2;use[ed]=1;
					above[e[id].u].pop_back();
					dfs(e[id].u);
				}
			}
		}
	};
	dfs(1);
	F(i,1,m+1){
		dbg(i,use[i]);
		if(use[i]==1)edges.push_back(i);
	}
	dbg(edges);

	// build one spanning tree, then let's see if we can build another without using his edges
	// when he does an edge and checks if it works, iff its in our tree, we delete that edge, and now we need to find a connection to it that isn't in his tree. If it connects to the converse of our subtree, we win, otherwise we need to like reorient everything?
	// we can afford an o(v) query
	// eh the data's probably weak and we can do an o(e) update of the tree

	vector<int>edges2;seen=vector<int>(n+1);
	function<void(int)>dfs2=[&](int u){
		if(seen[u])return;
		seen[u]=1;
		for(int id=head[u];id!=0;id=e[id].nxt){
			if(!seen[e[id].u] and use[id]!=1){
				edges2.push_back(id);
				dfs2(e[id].u);
			}
		}
	};
	dfs2(1);
	dbg(edges2.size(),edges2);
	if(edges.size()==n-1 and edges2.size()==n-1){
		F(i,0,n-1)cout<<edges[i]<<" \n"[i==n-2];
		F(i,0,n-1)cout<<edges2[i]<<" \n"[i==n-2];
	}else{
		cout<<"NONE\n";
	}

}

• Subtask 1: 0 / 4
• Subtask 2: 4 / 4
• Subtask 3: 4 / 4
• Subtask 4: 4 / 4
• Subtask 5: 4 / 4
• Subtask 6: 4 / 4
• Subtask 7: 4 / 4
• Subtask 8: 4 / 4
• Subtask 9: 4 / 4
• Subtask 10: 4 / 4
• Subtask 11: 4 / 4
• Subtask 12: 4 / 4
• Subtask 13: 4 / 4
• Subtask 14: 4 / 4
• Subtask 15: 4 / 4
• Subtask 16: 4 / 4
• Subtask 17: 4 / 4
• Subtask 18: 4 / 4
• Subtask 19: 4 / 4
• Subtask 20: 4 / 4
• Subtask 21: 0 / 5
• Subtask 22: 0 / 5
• Subtask 23: 0 / 5
• Subtask 24: 0 / 5