Submission #1296725

#	Time	Username	Problem	Language	Result	Execution time	Memory
1296725		okahak71	KOVANICE (COI15_kovanice)	C++20	50 / 100	69 ms	12900 KiB

kovanice

#include <bits/stdc++.h>
#define ll long long
#define endl '\n'
using namespace std;

struct DSU{
    vector<ll>e;
    DSU(ll n){
        e.assign(n + 1, -1);
    }
    ll find(ll x){
        if(e[x] < 0) return x;
        return e[x] = find(e[x]);
    }
    bool unite(ll a, ll b){
        a = find(a), b = find(b);
        if(a == b) return 0;
        if(e[a] > e[b]) swap(a, b);
        e[a] += e[b]; e[b] = a;
        return 1;
    }
};

void _(){
    ll n, m, q; cin >> n >> m >> q;
    DSU dsu(m); vector<pair<char, pair<ll, ll>>>v(q);
    for(ll i = 0; i < q; i++){
        ll a, b; char c; cin >> a >> c >> b;
        v[i] = {c, {a, b}}; if(c != '=') continue;
        dsu.unite(a, b);
    }
    vector<ll>ans(m + 1, -1);
    for(ll i = 0; i < q; i++){
        if(v[i].first == '=') continue;
        ll a = v[i].second.first; a = dsu.find(a);
        ll b = v[i].second.second; b = dsu.find(b);
        if(a == b){cout << -1 ; return ;}
        if(v[i].first == '>') swap(a, b);
        ans[a] = 1, ans[b] = 2;
    }
    for(ll i = 1; i <= m; i++){
        ll k = dsu.find(i);
        if(ans[k] == -1) cout << "?";
        else cout << "K" << ans[k]; cout << endl;
    }
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0); _();
}

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