oj.uz

Submission #40013

# Submission time Handle Problem Language Result Execution time Memory
40013 2018-01-25T08:53:17 Z 5ak0 KOVANICE (COI15_kovanice) C++14
100 / 100
 493 ms 57600 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:70: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:78: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 6 ms 33760 KB Output is correct
2 Correct 5 ms 33892 KB Output is correct

Subtask #2
40.0 / 40.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 35928 KB Output is correct
2 Correct 47 ms 35920 KB Output is correct
3 Correct 49 ms 35920 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 401 ms 47508 KB Output is correct
2 Correct 387 ms 47144 KB Output is correct
3 Correct 412 ms 47108 KB Output is correct
4 Correct 466 ms 57456 KB Output is correct
5 Correct 493 ms 57600 KB Output is correct