Submission #242646

#	Time	Username	Problem	Language	Result	Execution time	Memory
242646		kingfran1907	KOVANICE (COI15_kovanice)	C++14	100 / 100	374 ms	36964 KiB

kovanice

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

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