oj.uz

Submission #485072

# Submission time Handle Problem Language Result Execution time Memory
485072 2021-11-06T02:58:46 Z AMC76 KOVANICE (COI15_kovanice) C++14
60 / 100
 79 ms 38572 KB 
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
#define pii pair<int, int>
#define endl '\n'
using namespace std;

int T, N, M, V, X, Y, parent[200100], size[200100], dp1[200100], dp2[200100];
char OP;
vector <pii> operasi;
vector <int> adj1[200100], adj2[200100];
string harga[200100];

int root(int u){
    if(u == parent[u]) return u;
    return parent[u] = root(parent[u]);
}

void join(int x, int y){
    int rx = root(x);
    int ry = root(y);
    if(rx == ry) return;
    if(ry > rx) swap(rx, ry);
    parent[ry] = rx;
    size[rx] += size[ry];
}

int dfs1(int u){
    if(dp1[u] != -1) return dp1[u];
    dp1[u] = 1;
    for(auto v : adj1[u]) dp1[u] = max(dp1[u], dfs1(v) + 1);
    return dp1[u];
}

int dfs2(int u){
    if(dp2[u] != -1) return dp2[u];
    dp2[u] = 1;
    for(auto v : adj2[u]) dp2[u] = max(dp2[u], dfs2(v) + 1);
    return dp2[u];
}

int main(){
    fastio;
    //cin >> T;
    //while(T--){
        cin >> N >> M >> V;

        operasi.clear();
        for(int i=1; i<=M; i++){
            parent[i] = i;
            size[i] = 1;
            harga[i] = "?";
            adj1[i].clear();
            adj2[i].clear();
        }

        memset(dp1, -1, sizeof(dp1));
        memset(dp2, -1, sizeof(dp2));

        for(int i=1; i<=V; i++){
            cin >> X >> OP >> Y;
            if(OP == '<') operasi.push_back({X, Y});
            else join(X, Y);
        }

        for(auto i : operasi){
            X = i.first;
            Y = i.second;
            adj1[root(X)].push_back(root(Y));
            adj2[root(Y)].push_back(root(X));
        }

        for(int i=1; i<=M; i++) if(root(i) == i) if(dfs1(i) + dfs2(i) == N + 1) harga[i] = "K" + to_string(dfs2(i));

        for(int i=1; i<=M; i++){
            cout << harga[root(i)] << endl;
            //if(i == M) cout << endl;
            //else cout << " ";
        }
    //}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 17612 KB Output is correct
2 Correct 9 ms 17612 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 23876 KB Output is correct
2 Correct 79 ms 24040 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 20136 KB Output is correct
2 Correct 27 ms 20160 KB Output is correct
3 Correct 28 ms 20184 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 27 ms 38572 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -