oj.uz

Submission #846258

# Submission time Handle Problem Language Result Execution time Memory
846258 2023-09-07T13:00:53 Z vjudge1 KOVANICE (COI15_kovanice) C++17
50 / 100
 200 ms 16328 KB 
#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);
    if(x == y)return;
    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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 9148 KB Output is correct
2 Correct 87 ms 9296 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 33 ms 860 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 200 ms 16328 KB Output isn't correct
2 Halted 0 ms 0 KB -