Submission #466965

#	Time	Username	Problem	Language	Result	Execution time	Memory
466965		SirCovidThe19th	KOVANICE (COI15_kovanice)	C++17	20 / 100	1038 ms	40364 KiB

kovanice

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