oj.uz

Submission #39907

# Submission time Handle Problem Language Result Execution time Memory
39907 2018-01-24T09:14:26 Z krauch KOVANICE (COI15_kovanice) C++14
100 / 100
 471 ms 57592 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 = 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() {
    #ifdef krauch
        freopen("input.txt", "r", stdin);
    #else
        //freopen(fname".in", "r", stdin);
        //freopen(fname".out", "w", stdout);
    #endif

    scanf("%d %d %d\n", &L, &n, &m);

    forn(i, 1, n) p[i] = i;

    vector < PII > tmp;
    forn(i, 1, m) {
        string s;
        getline(cin, s);
        scanf("\n");
        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) printf("?\n");
        else printf("K%d\n", ans[getp(i)]);
    }

	return 0;
}

Compilation message

kovanice.cpp: In function 'int main()':
kovanice.cpp:81:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d\n", &L, &n, &m);
                                    ^
kovanice.cpp:89:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("\n");
                    ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 33760 KB Output is correct
2 Correct 3 ms 33892 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 39952 KB Output is correct
2 Correct 150 ms 40124 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 35928 KB Output is correct
2 Correct 52 ms 35920 KB Output is correct
3 Correct 46 ms 35920 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 420 ms 47512 KB Output is correct
2 Correct 422 ms 47144 KB Output is correct
3 Correct 390 ms 47108 KB Output is correct
4 Correct 462 ms 57456 KB Output is correct
5 Correct 471 ms 57592 KB Output is correct