oj.uz

Submission #24093

# Submission time Handle Problem Language Result Execution time Memory
24093 2017-05-30T15:21:14 Z chpipis KOVANICE (COI15_kovanice) C++11
100 / 100
 293 ms 26852 KB 
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pf push_front
#define iter(v, i) for (__typeof__((v).begin()) i = (v).begin(); i != (v).end(); i++)
#define fast_io_without_cstdio ios_base::sync_with_stdio(false), cin.tie(NULL)
#define all(v) (v).begin(), (v).end()

#ifdef __linux__
#define gc getchar_unlocked
#define pc putchar_unlocked
#else
#define gc getchar
#define pc putchar
#endif

#if __cplusplus <= 199711L
template<class BidirIt>
BidirIt prev(BidirIt it, typename iterator_traits<BidirIt>::difference_type n = 1) {
    advance(it, -n);
    return it;
}

template<class ForwardIt>
ForwardIt next(ForwardIt it, typename iterator_traits<ForwardIt>::difference_type n = 1) {
    advance(it, n);
    return it;
}
#endif

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef long double ldouble;

const double EPS = 1e-9;
const double PI = 3.141592653589793238462;

template<typename T>
inline T sq(T a) { return a * a; }

//#ifdef LOCAL_MACHINE
//#endif

const int MAXN = 3e5 + 5;

int p[MAXN];
vi gr[MAXN];
bool visit[MAXN];
vi seq;
int big[MAXN], small[MAXN];

int fin(int x) {
    return (p[x] == -1 ? x : p[x] = fin(p[x]));
}

void join(int x, int y) {
    x = fin(x), y = fin(y);
    if (x != y) {
        p[x] = y;
    }
}

void topo(int u) {
    visit[u] = true;
    for (auto v : gr[u])
        if (!visit[v])
            topo(v);
    seq.pb(u);
}

int main() {
    //freopen("", "rt", stdin);
    //freopen("", "wt", stdout);
    int n, m, v;
    scanf("%d %d %d", &n, &m, &v);
    memset(p, -1, sizeof p);
    vii ed;
    while (v--) {
        int a, b;
        char type;
        scanf("%d%c%d", &a, &type, &b);
        if (type == '=')
            join(a, b);
        else
            ed.pb(mp(a, b));
    }
    for (auto it : ed)
        gr[fin(it.fi)].pb(fin(it.se));
    for (int i = 1; i <= m; i++) {
        int cur = fin(i);
        sort(all(gr[cur]));
        gr[cur].resize(unique(all(gr[cur])) - gr[cur].begin());
    }
    for (int i = 1; i <= m; i++) {
        int cur = fin(i);
        if (!visit[cur]) topo(cur);
    }
    for (auto u : seq) {
        small[u] = 0;
        for (auto v : gr[u])
            small[u] = max(small[u], small[v] + 1);
    }
    reverse(all(seq));
    for (auto u : seq) {
        for (auto v : gr[u])
            big[v] = max(big[v], big[u] + 1);
    }
    for (int i = 1; i <= m; i++) {
        int cur = fin(i);
        if (big[cur] + small[cur] + 1 == n)
            printf("K%d\n", big[cur] + 1);
        else
            printf("?\n");
    }
    return 0;
}

Compilation message

kovanice.cpp: In function 'int main()':
kovanice.cpp:82:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &n, &m, &v);
                                  ^
kovanice.cpp:88:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%c%d", &a, &type, &b);
                                       ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 12864 KB Output is correct
2 Correct 0 ms 12864 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 16264 KB Output is correct
2 Correct 93 ms 16348 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 14504 KB Output is correct
2 Correct 29 ms 14496 KB Output is correct
3 Correct 29 ms 14496 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 279 ms 20908 KB Output is correct
2 Correct 253 ms 20620 KB Output is correct
3 Correct 289 ms 20600 KB Output is correct
4 Correct 273 ms 26796 KB Output is correct
5 Correct 293 ms 26852 KB Output is correct