#include <bits/stdc++.h>
using namespace std;
array<int, 3> f(string s) {
int i = 0, x = 0;
array<int, 3> a;
while (s[i] != '<' && s[i] != '>' && s[i] != '=') {
x*=10;
x += (s[i] - '0');
i++;
}
a[0] = x, a[1] = (s[i] == '<' ? 0 : (s[i] == '>' ? 1 : 2));
x = 0, i++;
while (i < s.size() && s[i] != '<' && s[i] != '>' && s[i] != '=') {
x*=10;
x += (s[i] - '0');
i++;
}
a[2] = x;
return a;
}
const int mxN = 3e5+2;
int p[mxN], sz[mxN], mx[mxN], ans[mxN];
bool visited[mxN];
vector<int> g[mxN], mxv[mxN], ord;
int findset(int s) {
if (s == p[s]) return s;
return p[s] = findset(p[s]);
}
void unite(int u, int v) {
u = findset(u), v = findset(v);
if (u == v) return;
if (sz[u] < sz[v]) swap(u, v);
p[v] = u;
sz[u] += sz[v];
}
void dfs(int s) {
visited[s] = 1;
for (auto u : g[s]) {
if (visited[u]) continue;
dfs(u);
}
ord.push_back(s);
}
void dfspush(int s, int x) {
visited[s] = 1;
ans[s] = x;
for (auto u : g[s]) {
if (visited[u]) continue;
dfspush(u, x-1);
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
iota(p, p+mxN, 0); fill(sz, sz+mxN, 1);
int n, m, v;
cin >> n >> m >> v;
vector<int> dir[mxN];
for (int i = 0; i < v; ++i) {
string s;
cin >> s;
auto [x, r, y] = f(s);
if (r == 2) {
unite(x, y);
}
else if (r == 1) {
dir[x].push_back(y);
}
else {
dir[y].push_back(x);
}
}
for (int i = 1; i <= m; ++i) {
for (auto u : dir[i]) {
g[findset(i)].push_back(findset(u));
}
}
for (int i = 1; i <= m; ++i) {
if (!visited[findset(i)]) {
dfs(findset(i));
}
}
ord.push_back(-1);
reverse(ord.begin(), ord.end());
for (int i = ord.size()-1; i >= 1; --i) {
for (auto u : g[ord[i]]) {
mx[ord[i]] = max(mx[ord[i]], mx[u] + 1);
}
for (auto u : g[ord[i]]) {
if(mx[u] + 1 == mx[ord[i]]) mxv[ord[i]].push_back(u);
}
}
fill(visited, visited+mxN, 0);
for (int i = 1; i < ord.size(); ++i) {
if (mx[ord[i]] == n-1 && !visited[ord[i]]) {
dfspush(ord[i], n);
}
}
for (int i = 1; i <= m; ++i) {
if (ans[findset(i)]) {
cout << "K" << ans[findset(i)] << '\n';
}
else {
cout << "K?" << '\n';
}
}
}
Compilation message
kovanice.cpp: In function 'std::array<int, 3> f(std::string)':
kovanice.cpp:15:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
15 | while (i < s.size() && s[i] != '<' && s[i] != '>' && s[i] != '=') {
| ~~^~~~~~~~~~
kovanice.cpp: In function 'int main()':
kovanice.cpp:96:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
96 | for (int i = 1; i < ord.size(); ++i) {
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
24412 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
50 ms |
32200 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
26716 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
142 ms |
44972 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
