oj.uz

Submission #846339

# Submission time Handle Problem Language Result Execution time Memory
846339 2023-09-07T13:41:43 Z vjudge1 KOVANICE (COI15_kovanice) C++17
100 / 100
 338 ms 85648 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, -1), out(N,-1);

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

int find_out(int node, vector<int>& out, set<int> g[])
{
    if(out[node] != -1)
        return out[node];
    out[node] = 0;
    for(int next : g[node])
    {
        out[node] = max(out[node], find_out(next, out, g) + 1);
    }
    return out[node];
}


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(find(v));
        for(auto v : rev[i])
            nrev[x].insert(find(v));
    }

    for(int i = 1; i <= m; ++i)
    {
        int x = find(i);
        if(nrev[x].size() == 0)
        {
            //cout << "noin " << i << ' ' << x << endl;
            find_out(x, out, ng);
        }
        if(ng[x].size() == 0)
        {
            //cout << "noout " << i << ' ' << x << endl;
            find_out(x, in, nrev);
        }
    }
    
    for(int i = 1; i <= m; ++i)
    {
        int x = find(i);
        if(in[x] + out[x] == n - 1)
        {
            cout << "K" << out[x] + 1 << 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 46172 KB Output is correct
2 Correct 12 ms 46428 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 55240 KB Output is correct
2 Correct 86 ms 55760 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 47704 KB Output is correct
2 Correct 34 ms 48728 KB Output is correct
3 Correct 36 ms 50512 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 317 ms 74660 KB Output is correct
2 Correct 295 ms 74496 KB Output is correct
3 Correct 298 ms 74172 KB Output is correct
4 Correct 331 ms 85648 KB Output is correct
5 Correct 338 ms 83748 KB Output is correct