Submission #485073

#	Time	Username	Problem	Language	Result	Execution time	Memory
485073		AMC76	KOVANICE (COI15_kovanice)	C++14	100 / 100	314 ms	47348 KiB

kovanice

#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 / 10
• Subtask 2: 40 / 40
• Subtask 3: 10 / 10
• Subtask 4: 40 / 40