# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
51340 |
2018-06-17T13:55:17 Z |
Milki |
KOVANICE (COI15_kovanice) |
C++14 |
|
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";
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
21624 KB |
Output is correct |
2 |
Correct |
20 ms |
21628 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
154 ms |
30784 KB |
Output is correct |
2 |
Correct |
132 ms |
32044 KB |
Output is correct |
# |
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 |
# |
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 |