#define fast ios::sync_with_stdio(false); cin.tie(0)
#define foru(i, k, n) for (long long i = k; i < n; i++)
#define ford(i, k, n) for (long long i = k; i >= n; i--)
#define pb push_back
#define mp make_pair
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <bitset>
#include <queue>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
typedef pair<ll, ll> pll;
const int sz = 5e5 + 5;
pair<pii, char> parse(string s) {
int cur = 0, ind = 0, len = s.length();
pair<pii, char> ret;
while (ind < len&&s[ind] >= '0'&&s[ind] <= '9') {
cur *= 10;
cur += (s[ind++] - '0');
}
ret.first.first = cur;
ret.second = s[ind++];
cur = 0;
while (ind < len&&s[ind] >= '0'&&s[ind] <= '9') {
cur *= 10;
cur += (s[ind++] - '0');
}
ret.first.second = cur;
return ret;
}
struct dsu {
int f[sz], p[sz];
int n;
dsu(int size) {
n = size;
foru(i, 0, n) {
p[i] = 1;
f[i] = i;
}
}
int father(int src) {
while (src != f[src])return f[src] = father(f[src]);
}
bool unite(int a, int b) {
int fa = father(a), fb = father(b);
if (fa == fb)return false;
if (p[fa] < p[fb])swap(fa, fb);
f[fb] = fa;
p[fa] = max(p[fb] + 1, p[fa]);
return true;
}
};
vector<int> unadj[sz], adj[sz], radj[sz];
int coins, mirk, v, ans[sz], indeg[sz], dp[sz];
dsu* d;
bitset<sz> isf, vis;
void input() {
cin >> coins >> mirk >> v;
d = new dsu(mirk);
foru(i, 0, v) {
string s;
cin >> s;
pair<pii, char> p = parse(s);
p.first.first--; p.first.second--;
switch (p.second) {
case '=':
d->unite(p.first.first, p.first.second);
break;
case '<':
unadj[p.first.first].pb(p.first.second);
break;
case '>':
unadj[p.first.second].pb(p.first.first);
break;
}
}
foru(i, 0, mirk) {
int myf = d->father(i);
isf[myf] = 1;
for (int x : unadj[i]) {
int otherf = d->father(x);
adj[myf].pb(otherf); radj[otherf].pb(myf);
indeg[otherf]++;
}
}
}
void dfs(int src) {
vis[src] = 1;
ans[src] = dp[src];
for (int x : radj[src]) {
if (!vis[x] && dp[x] == dp[src] - 1)dfs(x);
}
}
int main() {
fast;
input();
queue<int> q;
foru(i, 0, mirk) {
if (isf[i] && indeg[i] == 0)q.push(i);
}
while (!q.empty()) {
int x = q.front(); q.pop();
dp[x] = 1;
for (int y : radj[x])dp[x] = max(dp[x], dp[y] + 1);
for (int y : adj[x]) {
indeg[y]--;
if (indeg[y] == 0)q.push(y);
}
}
foru(i, 0, mirk) {
if (dp[i] == coins)dfs(i);
}
foru(i, 0, mirk) {
int myf = d->father(i);
if (ans[myf] != 0)cout << 'K' << to_string(ans[myf]) << '\n';
else cout << "?\n";
}
return 0;
}
Compilation message
kovanice.cpp: In member function 'int dsu::father(int)':
kovanice.cpp:51:2: warning: control reaches end of non-void function [-Wreturn-type]
51 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
355 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
347 ms |
524288 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
348 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
353 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
