Submission #846175

#	Time	Username	Problem	Language	Result	Execution time	Memory
846175		vjudge1	KOVANICE (COI15_kovanice)	C++17	50 / 100	160 ms	31320 KiB

kovanice

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

#define ll long long
const int N = 3e5 + 5, MOD = 1e9 + 7;

vector<ll> adj[N], vec[N];
ll n, m, v, ans[N], flag = 1, in[N], out[N];

void dfs(int node)
{
	for(auto to : adj[node])
	{
		if(ans[to] != 0 and ans[node] == ans[to])
		{
			flag = 0;
		}
		else if(ans[to] == 0)
		{
			ans[to] = ans[node] + 1;
			if(ans[to] > n)
				flag = 0;
			dfs(to);
		}
	}

	for(auto i : vec[node])
	{
		if(ans[i] != 0 and ans[i] != ans[node])
		{
			flag = 0;
		}
		else if(ans[i] == 0)
		{
			ans[i] = ans[node];
			dfs(i);
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n >> m >> v;

	for(int i = 0; i < v; i++)
	{
		int a, b;
		char ch;

		cin >> a >> ch >> b;

		if(ch == '<')
		{
			adj[a].push_back(b);
			out[a]++;
			in[b]++;
		}
		else
		{
			vec[a].push_back(b);
			vec[b].push_back(a);
		}
	}

	for(int i = 1; i <= m; i++)
	{
		if(in[i] == 0 and out[i] > 0)
		{
			ans[i] = 1;
			dfs(i);
		}
	}

	if(!flag)
	{
		cout << -1 << '\n';
		return 0;
	}

	for(int i = 1; i <= m; i++)
	{
		if(ans[i] == 0)
		{
			cout << "?" << '\n';
		}
		else
		{
			cout << "K" << ans[i] << '\n';
		}
	}
}

• Subtask 1: 10 / 10
• Subtask 2: 40 / 40
• Subtask 3: 0 / 10
• Subtask 4: 0 / 40