oj.uz

Submission #466965

# Submission time Handle Problem Language Result Execution time Memory
466965 2021-08-21T05:08:15 Z SirCovidThe19th KOVANICE (COI15_kovanice) C++17
20 / 100
 1038 ms 40364 KB 
#include <bits/stdc++.h>
using namespace std; 

const int mx = 3e5 + 5;

int n, m, k, bst[mx][2], vis[mx][2]; vector<pair<int, int>> adj[mx][2];

void dfs(int i, int dir){
    vis[i][dir] = 1; 
    for (auto x : adj[i][dir]){
        if (!vis[x.first][dir]) dfs(x.first, dir);
        bst[i][dir] = max(bst[i][dir], bst[x.first][dir] + x.second);
    }
}

int main(){
	cin >> n >> m >> k; 
    for (int i = 0; i < k; i++){
        int a, b; char c; cin >> a >> c >> b; 
        adj[a][0].push_back({b, c == '<'});
        adj[b][1].push_back({a, c == '<'});
        if (c == '='){
            adj[a][1].push_back({b, 0});
            adj[b][0].push_back({a, 0});
        }
    }
    for (int i = 1; i <= m; i++)
        dfs(i, 0), dfs(i, 1);
    for (int i = 1; i <= m; i++)
        cout<<(bst[i][0] + bst[i][1] + 1 == n ? "K" + to_string(bst[i][1] + 1) : "?")<<endl;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 14412 KB Output is correct
2 Correct 12 ms 14404 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 486 ms 25736 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 17964 KB Output is correct
2 Correct 72 ms 18028 KB Output is correct
3 Correct 75 ms 18116 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 1038 ms 40364 KB Output isn't correct
2 Halted 0 ms 0 KB -