oj.uz

Submission #846371

# Submission time Handle Problem Language Result Execution time Memory
846371 2023-09-07T14:07:17 Z vjudge1 KOVANICE (COI15_kovanice) C++17
20 / 100
 214 ms 34840 KB 
#include <bits/stdc++.h>
using namespace std;

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

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

void f(int node)
{
	visited[node] = true;
	dp[node] = 1;

	ll mx = 0;

	for(auto p : adj[node])
	{
		if(!visited[p[0]])
			f(p[0]);
		mx = max(mx, dp[p[0]]);
	}

	dp[node] += mx;
	for(int i = 0; i < adj[node].size(); i++)
	{
		if(dp[adj[node][i][0]] == mx)
		{
			adj[node][i][1] = 1;
		}
	}
}

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

	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];
	}
}

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, 0});
			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)
		{
			f(i);
		}
	}

	memset(visited, 0, sizeof(visited));

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

	for(int node = 1; node <= m; node++)
	{
		if(ans[node] != 0)
		{
			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];
			}
		}
	}

	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';
	}
}

Compilation message

kovanice.cpp: In function 'void f(int)':
kovanice.cpp:27:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |  for(int i = 0; i < adj[node].size(); i++)
      |                 ~~^~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 40.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 26716 KB Output is correct
2 Correct 18 ms 26788 KB Output is correct
3 Correct 24 ms 26640 KB Output is correct

Subtask #4
0 / 40.0

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