oj.uz

Submission #846379

# Submission time Handle Problem Language Result Execution time Memory
846379 2023-09-07T14:11:45 Z vjudge1 KOVANICE (COI15_kovanice) C++17
10 / 100
 249 ms 46420 KB 
#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

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.0

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

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 62 ms 34872 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 22 ms 34904 KB Output is correct
2 Correct 21 ms 34844 KB Output is correct
3 Correct 22 ms 34916 KB Output is correct

Subtask #4
0 / 40.0

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