oj.uz

Submission #39905

# Submission time Handle Problem Language Result Execution time Memory
39905 2018-01-24T09:06:19 Z krauch KOVANICE (COI15_kovanice) C++14
20 / 100
 215 ms 142844 KB 
/*
 _    _    _______   _    _
| |  / /  |  _____| | |  / /
| | / /   | |       | | / /
| |/ /    | |_____  | |/ /
| |\ \    |  _____| | |\ \
| | \ \   | |       | | \ \
| |  \ \  | |_____  | |  \ \
|_|   \_\ |_______| |_|   \_\

*/
#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 = 2e6 + 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;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 129136 KB Output is correct
2 Correct 36 ms 129136 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 64 ms 135284 KB Execution killed because of forbidden syscall writev (20)
2 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 131260 KB Output is correct
2 Correct 43 ms 131252 KB Output is correct
3 Correct 30 ms 131252 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 215 ms 142844 KB Execution killed because of forbidden syscall writev (20)
2 Halted 0 ms 0 KB -