oj.uz

Submission #384296

# Submission time Handle Problem Language Result Execution time Memory
384296 2021-04-01T09:26:45 Z Sara KOVANICE (COI15_kovanice) C++14
100 / 100
 337 ms 56036 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define ll long long int
#define F first
#define S second
#define pb push_back

const ll N = 3e5 + 5;
const ll LOG = 20;
const ll MOD = 1e9 + 7;
const ll INF = 1e9 + 5;

int n, m, k;
int E = 0;
pair <int, int> e[N];
vector <int> g[N], gr[N];
int par[N];
vector <int> in[N];
int l[N], r[N], ans[N];

int get_par(int v){
    if (!par[v]) return v;
    return v = get_par(par[v]);
}

inline void uni(int u, int v){
    u = get_par(u);
    v = get_par(v);
    if (u == v) return;
    if ((int)in[v].size() < (int)in[u].size()){
        swap(u, v);
    }
    par[u] = v;
    for (int i : in[u]){
        in[v].pb(i);
    }
    in[u] = {};
    return;
}

bool mark[N];
vector <int> dag;
void dfs(int v){
    mark[v] = 1;
    for (int u : g[v]){
        if (!mark[u]){
            dfs(u);
        }
    }
    dag.pb(v);
    return;
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m >> k;
    for (int v = 1; v <= m; v ++){
        in[v].pb(v);
    }
    for (int i = 0; i < k; i ++){
        string s;
        cin >> s;
        int p = 0;
        int u = 0, v = 0;
        while (s[p] != '=' && s[p] != '<'){
            u = u * 10 + (s[p] - '0');
            p ++;
        }
        char c = s[p]; p ++;
        while (p < (int)s.size()){
            v = v * 10 + (s[p] - '0');
            p ++;
        }
       if (c == '='){
            uni(u, v);
        }
        else {
            e[E] = {u, v};
            E ++;
        }
    }
    for (int i = 0; i < E; i ++){
        int u = get_par(e[i].F);
        int v = get_par(e[i].S);
        g[u].pb(v); gr[v].pb(u);
    }
    for (int v = 1; v <= m; v ++){
        if (!par[v] && !mark[v]){
            dfs(v);
        }
    }
    for (int v : dag){
        for (int u : g[v]){
            if (!mark[u]){
                r[v] = max(r[v], r[u]);
            }
        }
        mark[v] = 0;
        r[v] ++;
    }
    reverse(dag.begin(), dag.end());
    for (int v : dag){
        for (int u : gr[v]){
            if (mark[u]){
                l[v] = max(l[v], l[u]);
            }
        }
        mark[v] = 1;
        l[v] ++;
    }
    for (int i = 1; i <= m; i ++){
        if (!par[i]){
            if (l[i] + r[i] - 1 == n){
                for (int j : in[i]){
                    ans[j] = l[i];
                }
            }
        }
    }
    for (int i = 1; i <= m; i ++){
        if (!ans[i]){
            cout << "?\n";
        }
        else {
            cout << 'K' << ans[i] << '\n';
        }
    }
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 21612 KB Output is correct
2 Correct 17 ms 21612 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 36704 KB Output is correct
2 Correct 118 ms 36836 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 24172 KB Output is correct
2 Correct 35 ms 24300 KB Output is correct
3 Correct 32 ms 24172 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 296 ms 51296 KB Output is correct
2 Correct 296 ms 50528 KB Output is correct
3 Correct 294 ms 50360 KB Output is correct
4 Correct 320 ms 55268 KB Output is correct
5 Correct 337 ms 56036 KB Output is correct