Submission #846231

#	Time	Username	Problem	Language	Result	Execution time	Memory
846231		MercubytheFirst	KOVANICE (COI15_kovanice)	C++14	0 / 100	408 ms	524288 KiB

kovanice

#include<bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;
#define pb push_back
#define endl '\n'
#define fi first
#define se second
#define fio ios_base::sync_with_stdio(false);cin.tie(NULL);
#define CDIV(a,b) (((a)+(b)-(1))/(b))
const ll inf = 1e17 + 5;
const ll mod = 1e9 + 7;
const ll N = 3e5 + 30;

 
int mod_(int a, int b)
{
    if(a >= 0)return a % b;
    a += (-a/b + 1) * b;
    return a % b;
}

vector<int>dsu;
vector<vector<int> >g;

int find(int x)
{
    if(dsu[x] < 0)return x;
    return dsu[x] = find(dsu[x]);
}

void unite(int x, int y)
{
    x = find(x);
    y = find(y);
    int szx = -dsu[x], szy = -dsu[y];

    if(szx < szy)
    {
        dsu[y] += dsu[x];
        dsu[x] = y;
    }
    else
    {
        dsu[x] += dsu[y];
        dsu[y] = x;
    }
}


void solve()
{
    //cout << "HI2" << endl;
    int n, m, q;
    cin >> n >> m >> q;
    dsu.resize(m + 1, -1);
    g.resize(m + 1);
    for(int i = 1; i <= q; ++i)
    {
        //cout << i << endl;
        string tmp;
        char c;
        cin >> c;
        while(c != '<' and c != '=' and c != '>')
        {
            tmp.pb(c);
            cin >> c;
        }
        int u, v;
        u = stoi(tmp);
        cin >> v;
        //cout << u << ' ' << c << ' ' << v << endl;
        if(c == '<')
        {
            g[v].pb(u);
        }
        else if(c == '=')
        {
            unite(u, v);
        }
        else if(c == '>')
        {
            g[u].pb(v);
        }
    }
    //cout << "HI" << endl;
    vector<int>in(m + 1), out(m + 1);

    for(int i = 1; i <= m; ++i)
    {
        int x = find(i);
        for(auto v : g[i])
            out[x]++, in[find(v)]++;
    }

    for(int i = 1; i <= m; ++i)
    {
        int x = find(i);
        if(out[x])
            cout << "K2" << endl;
        else if(in[x])
            cout << "K1" << endl;
        else
            cout << "?" << endl;
    }

}

int main()
{
    //fio;
    //int t; cin >> t; while(t--)
    {
        solve();
    }
}

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