Submission #1004687

#	Time	Username	Problem	Language	Result	Execution time	Memory
1004687		ulianamalanyak	Usmjeravanje (COCI22_usmjeravanje)	C++14	0 / 110	10 ms	19036 KiB

Main

#include "bits/stdc++.h"
 
using namespace std;
 
#define endl '\n'
#define INF 1000000000000
#define mp make_pair
 
typedef int ll;
 
const int DIM=2e5+7;

ll n,m,k;
vector< pair<ll,ll> > a[DIM],b[DIM],flights;
ll mark[DIM];
vector<ll> v[2*DIM],topological;
ll vis[DIM*2];
ll scc[2*DIM];

void dfs(ll u, ll par)
{
	vis[u]=1;

	for (auto x:v[u])
	{
		if (vis[x]) continue;
		dfs(x,u);
	}

	//cout << u << ' ' << par << endl;
	topological.push_back(u);
}

void dfs2(ll u)
{
	scc[u]=1;

	for (auto x:v[u])
	{
		if (scc[x]) continue;
		//cout << "go " << x << "from " << u << endl;
		dfs2(x);
	}
	//cout << u << " ";
}

int main()
{
    //freopen ("input.txt","r",stdin);
    //freopen ("output.txt","w",stdout);
    
    cin >> n >> m;

	cin >> k;

	for (int i=1;i<=k;i++)
	{
		int x,y;
		cin >> x >> y;
		a[x].push_back(mp(y,i));
		b[y].push_back(mp(x,i));
		flights.push_back(mp(x,y));
	}

	ll x=1;
	ll y=1;
	while(x<=n)
	{
		if (a[x].size()==0)
		{
			x++;
			continue;
		}

		bool fl=0;
		ll lim=-1;
		ll num=0;
		for (auto y:a[x])
		{
			if (y.first>lim)
			{
				lim=y.first;
				num=y.second;
			}
		}
		mark[num]=1;

		for (auto y:a[x])
		{
			if (mark[y.second]==0) mark[y.second]=1;
		}
		//cout << "start " << x << " " << y << " " << lim << endl; 

		while(1)
		{
			//cout << x << ' ' << y << " " << lim << " " << fl << endl;
			if (!fl)
			{
				bool check=1;
				if (y==lim)
				{
					for (auto to:b[y])
					{
						if (mark[to.second]==0)
						{
							check=0;
							break;
						}
					}

					if (check) 
					{
						y++;
						x++;
						break;
					}
				}
				
				ll lim_x=x;

				for (;y<=lim;y++)
				{
					if(b[y].size()==0) continue;

					for (auto t:b[y])
					{
						if (mark[t.second]!=0) {continue;cout << "! " << y << endl;}
						mark[t.second]=2;
						//cout << "here 2 " << t.second << endl;
						lim_x=max(lim_x,t.first);
					}
				}
				y--;
				lim=lim_x;
				fl=1;
			}
			else
			{
				bool check=1;
				if (x==lim)
				{
					for (auto to:a[x])
					{
						if (mark[to.second]==0)
						{
							check=0;
							break;
						}
					}

					if (check) 
					{
						y++;
						x++;
						break;
					}
				}
				
				ll lim_y=y;

				for (;x<=lim;x++)
				{
					if(a[x].size()==0) continue;

					for (auto t:a[x])
					{
						if (mark[t.second]!=0) continue;
						mark[t.second]=1;
						//cout << "here 1 " << t.second << endl;
						lim_y=max(lim_y,t.first);
					}
				}
				x--;
				lim=lim_y;
				fl=0;
			}
		}
	}

	for (int i=1;i<n;i++)
	{
		v[2*i-1].push_back(2*(i+1)-1);
	}
	for (int i=1;i<m;i++)
	{
		v[2*i].push_back(2*(i+1));
	}

	for (int i=1;i<=k;i++)
	{
		ll x=flights[i-1].first;
		ll y=flights[i-1].second;
		if (mark[i]==1)
		{
			v[2*y].push_back(2*x-1);
		}
		else
		{
			v[2*x-1].push_back(2*y);
		}
	}

	for (int i=1;i<=n;i++)
	{
		if (!vis[2*i-1]) dfs(2*i-1,2*i-1);
	}
	for (int i=1;i<=m;i++)
	{
		if (!vis[2*i]) dfs(2*i,2*i);
	}

	//reverse(topological.begin(),topological.end());

	ll c=0;
	for (auto x:topological)
	{
		//cout << x << endl;
		if (scc[x]==0) 
		{
			dfs2(x);//cout << endl;
			c++;
		}
	}

	cout << c << endl;

	for (int i=1;i<=k;i++)
	{
		if (mark[i]==1) cout << 1 << " ";
		else cout << 0 << " ";
	}
  
    return 0;
}

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