oj.uz

Submission #485073

# Submission time Handle Problem Language Result Execution time Memory
485073 2021-11-06T03:00:46 Z AMC76 KOVANICE (COI15_kovanice) C++14
100 / 100
 314 ms 47348 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[300100], size[300100], dp1[300100], dp2[300100];
char OP;
vector <pii> operasi;
vector <int> adj1[300100], adj2[300100];
string harga[300100];
 
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 12 ms 26200 KB Output is correct
2 Correct 13 ms 26188 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 31136 KB Output is correct
2 Correct 94 ms 31424 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 27976 KB Output is correct
2 Correct 27 ms 28068 KB Output is correct
3 Correct 33 ms 27976 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 257 ms 42776 KB Output is correct
2 Correct 224 ms 42040 KB Output is correct
3 Correct 227 ms 41936 KB Output is correct
4 Correct 279 ms 46648 KB Output is correct
5 Correct 314 ms 47348 KB Output is correct