oj.uz

Submission #846266

# Submission time Handle Problem Language Result Execution time Memory
846266 2023-09-07T13:04:48 Z vjudge1 KOVANICE (COI15_kovanice) C++17
50 / 100
 252 ms 74456 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(N, -1);
vector<int>g[N], rev[N];
set<int> ng[N], nrev[N];
vector<int>in(N), out(N);

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(x == y)return;
    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;

    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);
            rev[u].pb(v);
        }
        else if(c == '=')
        {
            unite(u, v);
        }
        else if(c == '>')
        {
            g[u].pb(v);
            rev[v].pb(u);
        }
    }
    //cout << "HI" << endl;
    for(int i = 1; i <= m; ++i)
    {
        int x = find(i);
        for(auto v : g[i])
            ng[x].insert(v);
        for(auto v : rev[i])
            nrev[x].insert(v);
    }

    for(int i = 1; i <= m; ++i)
    {
        if(ng[find(i)].size())
            cout << "K2" << endl;
        else if(nrev[find(i)].size())
            cout << "K1" << endl;
        else
            cout << "?" << endl;
    }

}

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 46428 KB Output is correct
2 Correct 12 ms 46212 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 55160 KB Output is correct
2 Correct 73 ms 55600 KB Output is correct

Subtask #3
0 / 10.0

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

Subtask #4
0 / 40.0

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