| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1318645 | ayaz | KOVANICE (COI15_kovanice) | C++20 | 0 ms | 0 KiB |
// Pain
#include <bits/stdc++.h>
/*
What we should do :
1. L = Find longest path in each component
2. L should be exactly n
3. Then ans[u] = dep[u]
*/
#include "debug.h"
#define vi vector<int>
#define vvi vector<vi>
#define eb emplace_back
#define pb push_back
#define ull unsigned long long
#define ll long long
#define all(v) v.begin(), v.end()
#define isz(v) (int)v.size()
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<bool> used;
vector<vector<pair<int, int>>> g;
vector<int> ans, dep, nodes, id;
void dfs(int u) {
u = id[u];
used[u] = 1;
for (auto &[v, w] : g[u]) {
v = id[v];
if (!used[v]) dfs(v);
dep[u] = max(dep[u], dep[v] + w);
}
}
int mx;
void dfs2(int u) {
u = id[u];
used[u] = 1;
nodes.push_back(u);
mx = max(mx, dep[u]);
for (auto &[v, w] : g[u]) {
v = id[v];
if (!used[v]) dfs2(v);
}
}
struct DSU {
vi p, sz;
int n, compo;
void init(int _n) {
n = _n;
compo = n;
p.resize(n + 1);
sz.resize(n + 1, 1);
for (int i = 1; i <= n; i++) p[i] = i;
}
int getpar(int x) {
if (p[x] != x) p[x] = getpar(p[x]);
return p[x];
}
void connect(int x, int y) {
int a = getpar(x);
int b = getpar(y);
if (a == b) return;
if (sz[a] < sz[b]) swap(a, b);
p[b] = a;
sz[a] += sz[b];
}
bool same(int x, int y) {
return getpar(x) == getpar(y);
}
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, v;
cin >> n >> m >> v;
g.resize(m + 1);
used.resize(m + 1);
ans.resize(m + 1, -1);
id.resize(m + 1);
dep.resize(m + 1, 0);
DSU d;
d.init(m);
vector<pair<int, int>> ed;
for (int i = 1; i <= v; i++) {
int a, c; char b;
cin >> a >> b >> c;
if (b != '=')
ed.push_back({a, c});
else {
d.connect(a, c);
}
}
for (int u = 1; u <= m; u++) {
id[u] = d.getpar(u);
}
for (auto [x, y] : ed) {
x = id[x];
y = id[y];
g[x].push_back({y, 1});
}
for (int u = 1; u <= m; u++) {
if (used[id[u]]) continue;
dfs(id[u]);
}
for (int u = 1; u <= m; u++) {
debug(dep[id[u]]);
for (auto &[v, w] : g[id[u]]) {
g[id[v]].push_back({u, w});
}
}
fill(all(used), 0);
for (int u = 1; u <= m; u++) {
if (used[id[u]]) continue;
mx = 0;
dfs2(id[u]);
if (mx == n - 1) {
debug(nodes);
for (auto &v : nodes) ans[id[v]] = n - dep[id[v]];
debug(ans);
}
nodes.clear();
}
for (int u = 1; u <= m; u++) {
if (ans[id[u]] == -1) {
cout << "?\n";
} else {
cout << "K" << ans[id[u]] << '\n';
}
}
return 0;
}