oj.uz

Submission #670738

# Submission time Handle Problem Language Result Execution time Memory
670738 2022-12-10T07:52:47 Z LunaMeme KOVANICE (COI15_kovanice) C++14
100 / 100
 298 ms 29872 KB 
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> ii;
typedef vector<pair<int, int>> vii;
typedef vector<int> vi;
typedef long long ll;
#define PB push_back
#define MP make_pair
#define FOR(i, x, y) for (int i = x; i < y ; i ++)
const int MAXM = 3e5 + 5;
int link[MAXM], size[MAXM];
int find(int a){
    return (a == link[a]? a : link[a] = find(link[a]));
}
void onion(int a, int b){
    a = find(a); b = find(b);
    if (a == b) return;
    if (size[a] < size[b]) swap(a, b);
    link[b] = a;
    size[a] += size[b];
}
vi adj[MAXM];
int dp[MAXM], val[MAXM];
int DP(int curr){
    if (dp[curr]) return dp[curr];
    dp[curr] = 1;
    for (auto next : adj[curr]){
        dp[curr] = max(dp[curr], 1 + DP(next));
    }
    return dp[curr];
}
void update(int curr, int V){
    if (val[curr]) return;
    if (dp[curr] == V){
        val[curr] = V;
        for (auto next : adj[curr]){
            update(next, V - 1);
        }        
    }
}
int main(){
    FOR(i, 0, MAXM){
        link[i] = i;
        size[i] = 1;
        val[i] = 0;
    }
    int n, m , v; cin >> n >> m >> v;
    vii edges;
    FOR(i, 0, v){ 
        int a, b; char c;
        cin >> a >> c >> b;
        if (c == '='){
            onion(a, b);
            continue;
        }
        if (c == '<') swap(a, b);
        edges.PB(MP(a,b));
    }
    for (auto e : edges){
        adj[find(e.first)].PB(find(e.second));
        //cout << find(e.first) << ' ' << find(e.second) << '\n';
    }
    FOR(i, 0, MAXM){
        if (DP(i) == n){
            update(i, n);
        }
    }
    FOR(i, 1, m + 1){
        if (val[find(i)]){
            cout << "K" << val[find(i)] << '\n';
        }
        else cout << "?\n";
    }
}

Subtask #1
10.0 / 10.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 14172 KB Output is correct
2 Correct 95 ms 15644 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 13252 KB Output is correct
2 Correct 50 ms 14064 KB Output is correct
3 Correct 51 ms 14028 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 266 ms 18724 KB Output is correct
2 Correct 259 ms 22328 KB Output is correct
3 Correct 252 ms 22160 KB Output is correct
4 Correct 291 ms 24480 KB Output is correct
5 Correct 298 ms 29872 KB Output is correct