Submission #51340

#	Time	Username	Problem	Language	Result	Execution time	Memory
51340		Milki	KOVANICE (COI15_kovanice)	C++14	100 / 100	417 ms	65680 KiB

kovanice

#include <bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define TRACE(x) cerr << #x << " = " << x << endl
#define _ << " " <<

typedef long long ll;
typedef pair<int, int> point;

const int MAXN = 3e5 + 5;

int n, m, v;
vector <int> lvl[MAXN], up[MAXN], down[MAXN];
vector <point> E;
int upVal[MAXN], downVal[MAXN];
int id[MAXN];
bool bio[MAXN];

void spoji(int x, int curr){
    bio[x] = true;
    id[x] = curr;

    for(auto it : lvl[x])
        if(!bio[it])
            spoji(it, curr);

}

int dfs1(int x){
    if(upVal[x]) return upVal[x];
    for(auto it : up[x])
        upVal[x] = max(upVal[x], dfs1(it));
    upVal[x] ++;
    return upVal[x];
}

int dfs2(int x){
    if(downVal[x]) return downVal[x];
    for(auto it : down[x])
        downVal[x] = max(downVal[x], dfs2(it));
    downVal[x] ++;
    return downVal[x];
}

int main(){

    ios_base::sync_with_stdio(false); cin.tie(0);

    cin >> n >> m >> v;
    REP(i, v){
        int a, b; char c;
        cin >> a >> c >> b;

        if(c == '<'){
            E.push_back(point(a, b));
        }
        else{
            lvl[a].push_back(b);
            lvl[b].push_back(a);
        }
    }

    int tijme = 0;
    FOR(i, 1, m + 1)
        if(!bio[i])
            spoji(i, tijme++);

    REP(i, (int)E.size()){
        down[id[E[i].first]].push_back(id[E[i].second]);
        up[id[E[i].second]].push_back(id[E[i].first]);
    }

    FOR(i, 1, m + 1){
        dfs1(id[i]);
        dfs2(id[i]);
    }

    FOR(i, 1, m + 1){
        if(upVal[id[i]] + downVal[id[i]] == n + 1)
            cout << 'K' << upVal[id[i]] << "\n";
        else
            cout << "?\n";
    }
}

• Subtask 1: 10 / 10
• Subtask 2: 40 / 40
• Subtask 3: 10 / 10
• Subtask 4: 40 / 40