oj.uz

Submission #1036214

# Submission time Handle Problem Language Result Execution time Memory
1036214 2024-07-27T05:35:07 Z vjudge1 Naboj (COCI22_naboj) C++17
0 / 110
 351 ms 19904 KB 
#include <bits/stdc++.h>

using namespace std;

const int M = 2e5 + 1;

vector<int> nei[M];
int cnt[M][2],dep[M];
bool vis[M];

void bfs(int u)
{
	queue<int> q;
	vis[u]=1;
	q.push(u);
	while (!q.empty())
	{
		int v=q.front();
		q.pop();
		for (int i:nei[v])
			if (!vis[i])
			{
				vis[i]=1;
				dep[i]=1+dep[v];
				q.push(i);
			}
	}
}

signed main()
{
	int n,m;
	cin>>n>>m;
	for (int i=0;i<m;i++)
	{
		int a,b;
		cin>>a>>b;
		nei[a].push_back(b);
		nei[b].push_back(a);
		cnt[a][0]++;
		cnt[b][1]++;
	}
	int v=-1,d=0;
	for (int i=1;i<=n;i++)
		if (!cnt[i][0] || !cnt[i][1])
		{
			v=i;
			if (cnt[i][0])
				d=1;
			break;
		}
	if (v==-1)
	{
		cout<<-1<<endl;
		return 0;
	}
	bfs(v);
	vector<pair<int,int>> ver;
	for (int i=1;i<=n;i++)
		ver.push_back({dep[i],i});
	sort(ver.rbegin(),ver.rend());
	cout<<ver.size()<<endl;
	for (auto i:ver)
		cout<<i.second<<' '<<(i.first+d)%2<<endl;
	
	return 0;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4952 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 351 ms 19904 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4952 KB Output isn't correct
2 Halted 0 ms 0 KB -