oj.uz

Submission #846443

# Submission time Handle Problem Language Result Execution time Memory
846443 2023-09-07T14:48:42 Z vjudge1 KOVANICE (COI15_kovanice) C++17
60 / 100
 2000 ms 29472 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 998244353;
const ll LOGN = 20;
const ll MAXN = 3e5 + 5;

vector<vector<int>> graph, inv;
int par[MAXN], sz[MAXN], indeg[MAXN];
int dist[MAXN];
int find(int node) {
	if (node == par[node])
		return node;
	return par[node] = find(par[node]);
}

void unite(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b)
		return ;
	if (sz[b] > sz[a])
		swap(a, b);
	par[b] = a;
	sz[a] += sz[b];
}

vector<int> type;
vector<pair<int,int>> edge;
int main() {
	fast
	int N, M, V;
	cin >> N >> M >> V;

	graph = vector<vector<int>>(M+1, vector<int>());
	inv = vector<vector<int>>(M+1, vector<int>());
	type = vector<int>(M+1, -1);
	for (int i = 1; i <= M; i++)
		par[i] = i, sz[i] = 1;

	for (int i = 0; i < V; i++) {
		string s;
		cin >> s;
		
		vector<int> v1, v2;
		int plc = -1;
		for (int i = 0; i < s.length(); i++) {
			if (s[i] != '=' && s[i] != '<')
				v1.push_back(s[i] - '0');
			else {
				plc = i;
				break;
			}
		}
		for (int i = plc + 1; i < s.length(); i++)
			v2.push_back(s[i] - '0');

		int now = 1;
		int l = 0, r = 0;
		while (v1.size()) {
			l += now * v1.back();
			now *= 10;
			v1.pop_back(); 
		}
		now = 1;
		while (v2.size()) {
			r += now * v2.back();
			now *= 10;
			v2.pop_back();
		}

		if (s[plc] == '=')
			unite(l, r);
		else
			edge.push_back({l, r});
	}

	for (int i = 0; i < edge.size(); i++) {
		edge[i].f = find(edge[i].f);
		edge[i].s = find(edge[i].s);
	}
	sort(edge.begin(), edge.end());
	edge.erase(unique(edge.begin(), edge.end()), edge.end());

	for (int i = 0; i < edge.size(); i++) {
		graph[edge[i].f].push_back(edge[i].s); 
		inv[edge[i].s].push_back(edge[i].f);
		indeg[edge[i].s]++;
	}

	queue<int> q;
	for (int i = 1; i <= M; i++) {
		if (i == find(i) && indeg[i] == 0)
			q.push(i);
	}

	while (!q.empty()) {
		int node = q.front();
		q.pop();

		for (auto u : graph[node]) {
			if (dist[u] >= dist[node] + 1)
				continue;
			dist[u] = dist[node] + 1;
			q.push(u);
		}
	}

	queue<pair<int,int>> q2;
	for (int i = 1; i <= M; i++) {
		if (i == find(i) && dist[i] + 1 == N)
			q2.push({i, N});
	}

	while (!q2.empty()) {
		int node = q2.front().f;
		int t = q2.front().s;
		q2.pop();

		if (type[node] != -1 || dist[node] + 1 != t || t == 0)
			continue;
		type[node] = t;

		for (auto u : inv[node])
			q2.push({u, t-1});
	}

	for (int i = 1; i <= M; i++) {
		if (type[find(i)] == -1)
			cout << "?" << endl;
		else
			cout << "K" << type[find(i)] << endl;
	}
}

Compilation message

kovanice.cpp: In function 'int main()':
kovanice.cpp:51:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |   for (int i = 0; i < s.length(); i++) {
      |                   ~~^~~~~~~~~~~~
kovanice.cpp:59:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |   for (int i = plc + 1; i < s.length(); i++)
      |                         ~~^~~~~~~~~~~~
kovanice.cpp:82:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |  for (int i = 0; i < edge.size(); i++) {
      |                  ~~^~~~~~~~~~~~~
kovanice.cpp:89:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |  for (int i = 0; i < edge.size(); i++) {
      |                  ~~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4440 KB Output is correct
2 Correct 3 ms 4444 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 272 ms 18888 KB Output is correct
2 Correct 302 ms 19148 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 5316 KB Output is correct
2 Correct 29 ms 5584 KB Output is correct
3 Correct 34 ms 5836 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2029 ms 29472 KB Time limit exceeded
2 Halted 0 ms 0 KB -