#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;
int 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);
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();
node = find(node);
for (auto u : graph[node]) {
int p = find(u);
if (dist[p] >= dist[node] + 1)
continue;
dist[p] = dist[node] + 1;
q.push(p);
}
}
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:84: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]
84 | for (int i = 0; i < edge.size(); i++) {
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4440 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4444 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
310 ms |
19012 KB |
Output is correct |
| 2 |
Correct |
272 ms |
18996 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
32 ms |
6352 KB |
Output is correct |
| 2 |
Correct |
40 ms |
6332 KB |
Output is correct |
| 3 |
Correct |
55 ms |
6608 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2061 ms |
29656 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
