oj.uz

Submission #846544

# Submission time Handle Problem Language Result Execution time Memory
846544 2023-09-07T19:26:59 Z serifefedartar KOVANICE (COI15_kovanice) C++17
100 / 100
 465 ms 28176 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;
int N, M, V;
int par[MAXN], sz[MAXN], indeg[MAXN];
int dist[MAXN], lng[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];
}

void dfs(int node) {
	if (graph[node].size() == 0)
		lng[node] = 0;
	for (auto u : graph[node]) {
		if (lng[u] == -1)
			dfs(u);
		lng[node] = max(lng[node], lng[u] + 1);
	}
}

vector<int> type;
void dfs2(int node, int need) {
	if (lng[node] != need - 1)
		return ;

	type[node] = N-need+1;
	for (auto u : graph[node]) {
		if (type[u] == -1)
			dfs2(u, need-1);		
	}
}

vector<pair<int,int>> edge;
int main() {
	fast
	memset(lng, -1, sizeof(lng));
	cin >> N >> M >> V;
 
	graph = 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++) {
		int l, r;
		char ch;
		cin >> l >> ch >> r;
		if (ch == '=')
			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);
		graph[edge[i].f].push_back(edge[i].s);
		indeg[edge[i].s]++;
	}

	for (int i = 1; i <= M; i++) {
		if (i == find(i) && indeg[i] == 0)
			dfs(i);
	}
 	
	for (int i = 1; i <= M; i++) {
		if (i == find(i) && lng[i] == N-1)
			dfs2(i, N);
	}

	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:76: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]
   76 |  for (int i = 0; i < edge.size(); i++) {
      |                  ~~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Correct 2 ms 4700 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 246 ms 13244 KB Output is correct
2 Correct 262 ms 13444 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 5844 KB Output is correct
2 Correct 14 ms 6096 KB Output is correct
3 Correct 15 ms 5868 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 413 ms 21400 KB Output is correct
2 Correct 419 ms 20764 KB Output is correct
3 Correct 407 ms 20792 KB Output is correct
4 Correct 408 ms 23948 KB Output is correct
5 Correct 465 ms 28176 KB Output is correct