Submission #241620

#	Time	Username	Problem	Language	Result	Execution time	Memory
241620		marlicu	KOVANICE (COI15_kovanice)	C++14	100 / 100	372 ms	44428 KiB

kovanice

#include <bits/stdc++.h>

using namespace std;

#define X first
#define Y second

typedef pair <int, int> pii;

const int MAXN = 3e5 + 5;

int n, m, v;

int pripada[MAXN];
int vece[MAXN];
int manje[MAXN];

vector <int> jednaki[MAXN];
vector <pii> veze;
vector <int> veze_vece[MAXN];
vector <int> veze_manje[MAXN];

void vaganje() {
    string s;
    cin >> s;

    int a, b = 0;
    char znak;

    unsigned t = -1;
    while (++t < s.size()) {
        if (s[t] == '=' || s[t] == '<') {
            znak = s[t]; a = b; b = 0;
        }
        else {
            b *= 10; b += (s[t] - '0');
        }
    }

    if (znak == '<') {
        veze.push_back({a, b});
    }

    else {
        jednaki[a].push_back(b);
        jednaki[b].push_back(a);
    }
}

void dodaj (int x, int o) {
    pripada[x] = o;
    for (auto nx : jednaki[x]) {
        if (pripada[nx]) continue;
        dodaj(nx, o);
    }
}

int nadi_manje (int x) {
    if (manje[pripada[x]]) return manje[x] = manje[pripada[x]];
    for (auto nx : veze_manje[x]) {
        manje[pripada[x]] = max(manje[pripada[x]], nadi_manje(nx));
    }

    return ++manje[pripada[x]];
}


int nadi_vece (int x) {
    if (vece[pripada[x]]) return vece[x] = vece[pripada[x]];
    for (auto nx : veze_vece[x]) {
        vece[pripada[x]] = max(vece[pripada[x]], nadi_vece(nx));
    }
    return ++vece[pripada[x]];
}

void poslozi_veze() {
    for (auto x : veze) {
        veze_vece[pripada[x.X]].push_back(pripada[x.Y]);
        veze_manje[pripada[x.Y]].push_back(pripada[x.X]);
    }
}

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

    cin >> n >> m >> v;
    for (int i = 0; i < v; i++) vaganje();
    for (int i = 1; i <= m; i++) {
        if (pripada[i]) continue;
        dodaj(i, i);
    }

    poslozi_veze();

    for (int i = 1; i <= m; i++) nadi_manje(i);
    for (int i = 1; i <= m; i++) nadi_vece(i);

    /*
    for (int i = 1; i <= m; i++) cout << pripada[i] << " "; cout << '\n';
    for (int i = 1; i <= m; i++) {
        cout << i << " : ";
        for (auto x : veze_manje[i]) cout << x << " ";
        cout << ": ";
        for (auto x : veze_vece[i]) cout << x << " ";
        cout << '\n';
    }

    for (int i = 1; i <= m; i++) cout << manje[i] << " "; cout << '\n';
    for (int i = 1; i <= m; i++) cout << vece[i] << " "; cout << '\n';
    */

    for (int i = 1; i <= m; i++) {
        if (manje[i] + vece[i] - 1 == n) {
            cout << "K" << manje[i] << "\n";
        }
        else cout << "?\n";
    }

    return 0;
}

Compilation message (stderr)

kovanice.cpp: In function 'void vaganje()':
kovanice.cpp:40:5: warning: 'znak' may be used uninitialized in this function [-Wmaybe-uninitialized]
     if (znak == '<') {
     ^~

• Subtask 1: 10 / 10
• Subtask 2: 40 / 40
• Subtask 3: 10 / 10
• Subtask 4: 40 / 40