oj.uz

Submission #242646

# Submission time Handle Problem Language Result Execution time Memory
242646 2020-06-28T14:33:43 Z kingfran1907 KOVANICE (COI15_kovanice) C++14
100 / 100
 374 ms 36964 KB 
#include <bits/stdc++.h>

using namespace std;
const int maxn = 3e5+10;

int n, m, k;
vector<int> graph[maxn], graph2[maxn];
int parr[maxn];
int dp[maxn], dp2[maxn];
vector< pair<int, int> > v;

int fin(int x) {
    if (parr[x] == x) return x;
    else return parr[x] = fin(parr[x]);
}

void merg(int a, int b) {
    a = fin(a);
    b = fin(b);
    if (a == b) return;

    int ra = rand() % 2;
    if (ra == 0) parr[a] = b;
    else parr[b] = a;
}

int f(int x) {
    int &ret = dp[x];
    if (ret != -1) return ret;

    ret = 0;
    for (int i = 0; i < graph[x].size(); i++) {
        int tren = graph[x][i];
        ret = max(ret, 1 + f(tren));
    }
    return ret;
}

int f2(int x) {
    int &ret = dp2[x];
    if (ret != -1) return ret;

    ret = 0;
    for (int i = 0; i < graph2[x].size(); i++) {
        int tren = graph2[x][i];
        ret = max(ret, 1 + f2(tren));
    }
    return ret;
}

int main() {
    srand(time(0));
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m >> k;
    for (int i = 1; i <= m; i++) parr[i] = i;
    for (int i = 0; i < k; i++) {
        string a;
        cin >> a;

        int x = 0, y = 0;
        char type;

        reverse(a.begin(), a.end());
        while (isdigit(a.back())) {
            x *= 10, x += a.back() - '0';
            a.pop_back();
        }
        type = a.back();
        a.pop_back();
        while (!a.empty()) {
            y *= 10, y += a.back() - '0';
            a.pop_back();
        }

        if (type == '=') merg(x, y);
        else {
            v.push_back(make_pair(x, y));
            //graph[x].push_back(y);
            //graph2[y].push_back(x);
        }
    }

    for (int i = 0; i < v.size(); i++) {
        int x = v[i].first;
        int y = v[i].second;
        x = fin(x), y = fin(y);

        graph[x].push_back(y);
        graph2[y].push_back(x);
    }

    memset(dp, -1, sizeof dp);
    memset(dp2, -1, sizeof dp2);
    for (int i = 1; i <= m; i++) {
        int x = fin(i);

        int a = f(x), b = f2(x);
        if (a + b + 1 == n) printf("K%d\n", b + 1);
        else printf("?\n");

        //printf("debug %d (%d) %d %d\n", i, x, a, b);
    }
    return 0;
}

Compilation message

kovanice.cpp: In function 'int f(int)':
kovanice.cpp:32:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < graph[x].size(); i++) {
                     ~~^~~~~~~~~~~~~~~~~
kovanice.cpp: In function 'int f2(int)':
kovanice.cpp:44:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < graph2[x].size(); i++) {
                     ~~^~~~~~~~~~~~~~~~~~
kovanice.cpp: In function 'int main()':
kovanice.cpp:85:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < v.size(); i++) {
                     ~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 16896 KB Output is correct
2 Correct 13 ms 16896 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 22388 KB Output is correct
2 Correct 92 ms 22512 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 19448 KB Output is correct
2 Correct 30 ms 19448 KB Output is correct
3 Correct 31 ms 19440 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 278 ms 31928 KB Output is correct
2 Correct 245 ms 31460 KB Output is correct
3 Correct 243 ms 31340 KB Output is correct
4 Correct 339 ms 36196 KB Output is correct
5 Correct 374 ms 36964 KB Output is correct