제출 #846156

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
846156		vjudge1	KOVANICE (COI15_kovanice)	C++17	50 / 100	165 ms	14604 KiB

kovanice

#include <bits/stdc++.h>
#define int long long int
#define MP make_pair
#define pb push_back
#define REP(i,n) for(int (i) = 0; (i) < (n); (i)++)
using namespace std;

const double EPS = 0.00001;
const int INF = 1e9+500;
const int MOD = 1e9+7;
const int N = 3e5+5;
const int K = 1505;
const int ALPH = 26;
int n,m,q,v;

struct DSU {
    vector<int> p, sz;

    DSU(int num) {
        p.resize(num+1);
        sz.resize(num+1);
    }
    void make_set(int x) {
        p[x] = x;
        sz[x] = 1;
    }
    int find_set(int x) {
        if(p[x] == x) return x;
        return p[x] = find_set(p[x]);
    }
    void union_set(int x, int y) {
        x = find_set(x);
        y = find_set(y);
        if(x == y) return;
        if(sz[x] < sz[y]) swap(x,y);
        p[y] = x;
        sz[x] += sz[y];
    }

};
vector<array<int,2> > eqs, ineqs;
vector<int> res;
void solve() {
    cin>>n>>m>>v;
    res.resize(m+1);
    for(int i = 0; i<v; i++) {
        int a,b;
        char op;
        cin>>a;
        cin>>op;
        cin>>b;
        if(op == '<') {
            ineqs.pb({a,b});
        }   
        else if(op == '=') {
            eqs.pb({a,b});
        }
        else assert(0);
    }   
    DSU ds(m); 
    for(int i = 1; i<=m; i++) {
        ds.make_set(i);
    }
    for(auto ind : eqs) {
        ds.union_set(ind[0], ind[1]);
    }
    for(auto ind : ineqs) {
        res[ ds.find_set(ind[0]) ] = 1;
        res[ ds.find_set(ind[1]) ] = 2;

    }
    for(int i = 1; i<=m; i++) {
        if(res[ ds.find_set(i) ] == 0) {
            cout<<"?\n";
            continue;
        }
        cout<<"K"<<res[ ds.find_set(i) ]<<"\n"; 
    } 

}   

signed main() {
    int test = 1;
    //cin>>test;
    while(test--) {
        solve();
    }
    
}

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