oj.uz

Submission #51340

# Submission time Handle Problem Language Result Execution time Memory
51340 2018-06-17T13:55:17 Z Milki KOVANICE (COI15_kovanice) C++14
100 / 100
 417 ms 65680 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 21624 KB Output is correct
2 Correct 20 ms 21628 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 30784 KB Output is correct
2 Correct 132 ms 32044 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 32044 KB Output is correct
2 Correct 42 ms 32044 KB Output is correct
3 Correct 43 ms 32044 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 417 ms 48544 KB Output is correct
2 Correct 358 ms 51888 KB Output is correct
3 Correct 342 ms 55596 KB Output is correct
4 Correct 396 ms 61044 KB Output is correct
5 Correct 416 ms 65680 KB Output is correct