oj.uz

답안 #846206

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
846206 2023-09-07T12:28:33 Z vjudge1 KOVANICE (COI15_kovanice) C++17
0 / 100
 388 ms 524288 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];

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;

    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;
    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]++;
        for(auto v : rev[i])
            in[x]++;
    }

    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();
    }
}

Compilation message

kovanice.cpp: In function 'void solve()':
kovanice.cpp:94:18: warning: unused variable 'v' [-Wunused-variable]
   94 |         for(auto v : g[i])
      |                  ^
kovanice.cpp:96:18: warning: unused variable 'v' [-Wunused-variable]
   96 |         for(auto v : rev[i])
      |                  ^

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 366 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 20564 KB Output is correct
2 Runtime error 388 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 369 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 370 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -