oj.uz

Submission #670737

# Submission time Handle Problem Language Result Execution time Memory
670737 2022-12-10T07:52:11 Z LunaMeme KOVANICE (COI15_kovanice) C++14
0 / 100
 314 ms 25336 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
0 / 10.0

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

Subtask #2
0 / 40.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 40.0

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