oj.uz

Submission #846175

# Submission time Handle Problem Language Result Execution time Memory
846175 2023-09-07T12:10:21 Z vjudge1 KOVANICE (COI15_kovanice) C++17
50 / 100
 160 ms 31320 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 19292 KB Output is correct
2 Correct 5 ms 19292 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 25852 KB Output is correct
2 Correct 48 ms 25500 KB Output is correct

Subtask #3
0 / 10.0

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

Subtask #4
0 / 40.0

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