Submission #846379

#	Time	Username	Problem	Language	Result	Execution time	Memory
846379		vjudge1	KOVANICE (COI15_kovanice)	C++17	10 / 100	249 ms	46420 KiB

kovanice

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

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

vector<ll> adjjj[N], 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];
	}
}

void asdasdasd(int node)
{
	for(auto to : adjjj[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;
			asdasdasd(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];
			asdasdasd(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, 0});
			adjjj[a].push_back(b);
			out[a]++;
			in[b]++;
		}
		else
		{
			vec[a].push_back(b);
			vec[b].push_back(a);
		}
	}


	if(n == 2)
	{
		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';
			}
		}
		return 0;
	}

	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 (stderr)

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: 0 / 10
• Subtask 2: 0 / 40
• Subtask 3: 10 / 10
• Subtask 4: 0 / 40