Submission #39907

#	Time	Username	Problem	Language	Result	Execution time	Memory
39907		krauch	KOVANICE (COI15_kovanice)	C++14	100 / 100	471 ms	57592 KiB

kovanice

/*
 _    _    _______   _    _
| |  / /  |  _____| | |  / /
| | / /   | |       | | / /
| |/ /    | |_____  | |/ /
| |\ \    |  _____| | |\ \
| | \ \   | |       | | \ \
| |  \ \  | |_____  | |  \ \
|_|   \_\ |_______| |_|   \_\

*/
#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 (stderr)

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 / 10
• Subtask 2: 40 / 40
• Subtask 3: 10 / 10
• Subtask 4: 40 / 40