Submission #670737

#	Time	Username	Problem	Language	Result	Execution time	Memory
670737		LunaMeme	KOVANICE (COI15_kovanice)	C++14	0 / 100	314 ms	25336 KiB

kovanice

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