# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
40012 |
2018-01-25T08:48:28 Z |
5ak0 |
KOVANICE (COI15_kovanice) |
C++14 |
|
2000 ms |
39480 KB |
/*
ID: 5ak0
PROG:
LANG: C++11
*/
#include <bits/stdc++.h>
#define fr first
#define sc second
#define pb push_back
#define mpr make_pair
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 1e9 + 7, MAXN = 3e5 + 10;
int n, m, v;
int l[MAXN], r[MAXN];
vector <int> g1[MAXN], g2[MAXN], gg[MAXN];
bool u[MAXN];
void dfs1(int v){
for (auto to : g1[v]){
l[to] = max(l[to], l[v] + 1);
dfs1(to);
}
}
void dfs2(int v){
for (auto to : g2[v]){
r[to] = min((r[to] == 0 ? INF : r[to]), r[v] - 1);
dfs2(to);
}
}
void dfs(int v){
u[v] = 1;
for (auto to : gg[v]){
if (u[to] == 0){
l[to] = l[v];
r[to] = r[v];
dfs(to);
}
}
}
int main(){
cin >> n >> m >> v;
for (int i = 1; i <= v; ++i){
int a, b;
char ch;
cin >> a >> ch >> b;
if (ch == '<'){
g1[a].pb(b);
g2[b].pb(a);
}
else{
gg[a].pb(b);
gg[b].pb(a);
}
}
for (int i = 1; i <= m; ++i){
if (g2[i].size() == 0 && g1[i].size() != 0){
l[i] = 1;
dfs1(i);
}
}
for (int i = 1; i <= m; ++i){
if (g1[i].size() == 0 && g2[i].size() != 0){
r[i] = n;
dfs2(i);
}
}
for (int i = 1; i <= m; ++i)
if (u[i] == 0 && l[i] != 0 && r[i] != 0)
dfs(i);
for (int i = 1; i <= m; ++i){
if (l[i] != r[i] || l[i] == 0 || r[i] == 0)
cout << "?\n";
else
cout << "K" << l[i] << "\n";
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
25884 KB |
Output is correct |
2 |
Correct |
6 ms |
25884 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
200 ms |
30636 KB |
Output is correct |
2 |
Correct |
189 ms |
30636 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2000 ms |
27072 KB |
Execution timed out |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2000 ms |
39480 KB |
Execution timed out |
2 |
Halted |
0 ms |
0 KB |
- |