Submission #1120745

#	Time	Username	Problem	Language	Result	Execution time	Memory
1120745		Fikrat_Asadzadeh	KOVANICE (COI15_kovanice)	C++14	50 / 100	567 ms	3656 KiB

kovanice

#include"bits/stdc++.h"
using namespace std;
 
#define int long long
const int mxN = 3e5+15;
 
struct Dsu {
    int ar[mxN];
    int Find(int u) {
        if (0 > ar[u]) {
            return u;
        } else {
            return ar[u] = Find(ar[u]);
        }
    }
    void Unite(int u, int v) {
        u = Find(u);
        v = Find(v);
        if (u == v) {
            return;
        }
        if (ar[u] > ar[v]) {
            swap(u, v);
        }
        ar[u] += ar[v];
        ar[v] = u;
    }
} dsu;
 
signed main() {
    int N, M, V;
    cin >> N >> M >> V;
    for (int i = 0; i < mxN; i ++) {
        dsu.ar[i] = -1;
    }
    int l = -1;
    int g = -1;
 
    for (int f = 0; f < V; f ++) {
        string S;
        cin >> S;
        int sz = S.size();
        int a = 0;
        int ps = 0;
        for (int i = 0; i < sz; i ++) {
            if (S[i] == '=' || S[i] == '<') {
                break;
            } else {
                a = a * 10 + S[i] - '0';
            }
            ps = i;
        }
        char c = S[ps + 1];
        int b = 0;
        for (int i = ps + 2; i < sz; i ++) {
            b = b * 10 + S[i] - '0';
        }
        if (c == '=') {
            dsu.Unite(a, b);
        } else {
            if (-1 != l && -1 != g) {
                dsu.Unite(l, a);
                dsu.Unite(g, b);
            }
            l = a, g = b;
        }
    }
    if (-1 == l && -1 == g) {
        for (int i = 0; i < M; i ++) {
            cout << '?' << endl;
        }
    } else {
        for (int i = 1; i <= M; i ++) {
            int u = dsu.Find(i);
            if (u == dsu.Find(l)) {
                cout << "K1" << endl;
            } else if (u == dsu.Find(g)) {
                cout << "K2" << endl;
            } else {
                cout << '?' << endl;
            }
        }
    }
}

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