/*
_ _ _______ _ _
| | / / | _____| | | / /
| | / / | | | | / /
| |/ / | |_____ | |/ /
| |\ \ | _____| | |\ \
| | \ \ | | | | \ \
| | \ \ | |_____ | | \ \
|_| \_\ |_______| |_| \_\
*/
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double ld;
typedef pair <int, int> PII;
typedef pair <ll, ll> PLL;
#define F first
#define S second
#define pb push_back
#define eb emplace_back
#define right(x) x << 1 | 1
#define left(x) x << 1
#define forn(x, a, b) for (int x = a; x <= b; ++x)
#define for1(x, a, b) for (int x = a; x >= b; --x)
#define mkp make_pair
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define y1 kekekek
#define fname ""
const ll ool = 1e18 + 9;
const int oo = 1e9 + 9, base = 1e9 + 7;
const ld eps = 1e-7;
const int N = 5e5 + 6;
int n, m, L, val[N], ans[N], p[N], r[N];
bool u[N];
vector < int > g[N], rg[N];
vector < PII > vec;
int getp(int v) {
return (p[v] == v ? v : getp(p[v]));
}
void unite(int v, int u) {
v = getp(v);
u = getp(u);
if (v == u) return;
if (r[v] == r[u]) r[v]++;
if (r[v] > r[u]) p[u] = v;
else p[v] = u;
}
int dfs(int v) {
if (u[v]) return val[v];
u[v] = 1;
int mn = L + 1;
for (auto to : g[v]) {
mn = min(mn, dfs(to));
}
val[v] = mn - 1;
vec.eb(val[v], v);
return val[v];
}
int main() {
ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);
#ifdef krauch
freopen("input.txt", "r", stdin);
#else
//freopen(fname".in", "r", stdin);
//freopen(fname".out", "w", stdout);
#endif
cin >> L >> n >> m;
forn(i, 1, n) p[i] = i;
vector < PII > tmp;
forn(i, 1, m) {
string s;
cin >> s;
int x = 0, pos = 0;
forn(j, 0, sz(s) - 1) {
if (s[j] > '9' || s[j] < '0') {
pos = j;
break;
}
x = x * 10 + (s[j] - '0');
}
int y = 0;
forn(j, pos + 1, sz(s) - 1) {
y = y * 10 + (s[j] - '0');
}
if (s[pos] == '=') unite(x, y);
if (s[pos] == '<') tmp.eb(x, y);
if (s[pos] == '>') tmp.eb(y, x);
}
for (auto it : tmp) {
g[getp(it.F)].eb(getp(it.S));
rg[getp(it.S)].eb(getp(it.F));
}
forn(i, 1, n) {
if (!u[getp(i)]) dfs(getp(i));
}
sort(all(vec));
for (auto it : vec) {
int v = it.S;
int mx = 0;
for (auto to : rg[v]) {
mx = max(mx, val[to]);
}
if (mx < val[v] - 1) {
ans[v] = -1;
val[v] = mx + 1;
}
else ans[v] = val[v];
}
forn(i, 1, n) {
if (ans[getp(i)] == -1) cout << "?\n";
else cout << "K" << ans[getp(i)] << "\n";
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
33920 KB |
Output is correct |
2 |
Correct |
3 ms |
33920 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
63 ms |
40068 KB |
Execution killed because of forbidden syscall writev (20) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
36044 KB |
Output is correct |
2 |
Correct |
15 ms |
36036 KB |
Output is correct |
3 |
Correct |
17 ms |
36036 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
183 ms |
47624 KB |
Execution killed because of forbidden syscall writev (20) |
2 |
Halted |
0 ms |
0 KB |
- |