Submission #563989

#	Time	Username	Problem	Language	Result	Execution time	Memory
563989		fuad27	Usmjeravanje (COCI22_usmjeravanje)	C++17	0 / 110	11 ms	19104 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 400'010;
vector<int> g[MAXN];
vector<int> g_rev[MAXN];
bool cmp(pair<pair<int,int>,int> a, pair<pair<int,int>,int> b) {
	if(a.first.first==b.first.first)return a.first.second > b.first.second;
	return a.first.first < b.first.first;
}
vector<int> topo;
vector<bool> used(MAXN);
void dfs(int v) {
	used[v] = true;
	for(int i:g[v])
		if(!used[i])
			dfs(i);
	topo.push_back(v);
}
int cnt;
void dfs2(int v) {
	used[v] = true;
	cnt++;
	for(int i:g_rev[v])
		if(!used[i])
			dfs2(i);
}
int32_t main () {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int a, b;
	cin >> a >> b;
	int m;
	cin >> m;
	for(int i = 1;i<a;i++) {
		g[i].push_back(i+1);
		g_rev[i+1].push_back(i);
	}
	for(int i = 1;i<b;i++) {
		g[i+a].push_back(i+1+a);
		g_rev[i+a+1].push_back(i+a);
	}
	vector<pair<pair<int,int>,int>> v(m);
	for(int i = 0;i<m;i++){
		cin>>v[i].first.first>>v[i].first.second;
		v[i].second=i;
	}
	sort(v.begin(), v.end(), cmp);
	int MAXY = 0;
	bool ans[m];
	for(int i = 0;i<m;i++) {
		if(v[i].first.second > MAXY) {
			g[v[i].first.second+a].push_back(v[i].first.first);
			g_rev[v[i].first.first].push_back(v[i].first.second+a);
			ans[v[i].second] = 1;
			MAXY=v[i].first.second;
		}
		else {
			g[v[i].first.first].push_back(v[i].first.second+a);
			g_rev[v[i].first.second+a].push_back(v[i].first.first);
			ans[v[i].second] = 0;
		}
	}
	for(int i = 1;i<=a;i++) {
		if(!used[i])
			dfs(i);
	}
	for(int i = 1;i<=b;i++) {
		if(!used[i+a])
			dfs(i+a);
	}
	reverse(topo.begin(), topo.end());
	used.assign(MAXN, 0);
	long long res=0;
	for(int i:topo) {
		cnt = 0;
		if(!used[i]) {
			dfs2(i);
			res++;
		}
	}
	cout << res << "\n";
	for(int i = 0;i<m;i++){
		cout<<ans[i]<<" ";
	}
	cout << "\n";
	return 0;
}

• Subtask 1: 0 / 20
• Subtask 2: 0 / 30
• Subtask 3: 0 / 60