Submission #1296705

#	Time	Username	Problem	Language	Result	Execution time	Memory
1296705		okahak71	KOVANICE (COI15_kovanice)	C++20	0 / 100	19 ms	16788 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<string>v(q);
    for(ll i = 0; i < q; i++){
        cin >> v[i];
        if(v[i][1] == '=') dsu.unite(v[i][0] - '0', v[i][2] - '0');
    }
    vector<array<ll, 2>>cnt(m + 1, {0, 0});
    for(ll i = 0; i < q; i++){
        if(v[i][1] == '=') continue;
        ll a = v[i][0] - '0'; a = dsu.find(a);
        ll b = v[i][2] - '0'; b = dsu.find(b);
        if(a == b){cout << -1; return ;} //impossible
        if(v[i][1] == '>') swap(a, b);
        cnt[a][1]++; cnt[b][0]++;
    }
    for(ll k = 1; k <= m; k++){
        //cout << cnt[i][0] << ' ' << cnt[i][1] << ' ';
        ll i = dsu.find(k);
        if(cnt[i][0] + cnt[i][1] + 1 < n) cout << "?";
        else if(cnt[i][0] + cnt[i][1] + 1 > n) {cout << -1; return ;} //impossible
        else cout << "K" << cnt[i][0] + 1; cout << endl;
    }
}

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

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