oj.uz

Submission #241620

# Submission time Handle Problem Language Result Execution time Memory
241620 2020-06-24T19:16:47 Z marlicu KOVANICE (COI15_kovanice) C++14
100 / 100
 372 ms 44428 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 21632 KB Output is correct
2 Correct 18 ms 21632 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 30708 KB Output is correct
2 Correct 113 ms 30704 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 24216 KB Output is correct
2 Correct 34 ms 24352 KB Output is correct
3 Correct 34 ms 24232 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 306 ms 43752 KB Output is correct
2 Correct 321 ms 43236 KB Output is correct
3 Correct 328 ms 42820 KB Output is correct
4 Correct 341 ms 43780 KB Output is correct
5 Correct 372 ms 44428 KB Output is correct