| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 104938 |
2019-04-09T20:25:33 Z |
Shtef |
KOVANICE (COI15_kovanice) |
C++14 |
|
874 ms |
42612 KB |
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;
typedef pair <int, int> pii;
#define x first
#define y second
#define mp make_pair
vector <int> ms[300005], fg[300005], topo[300005];
int n, m, v, link[300005], sz[300005], koja[300005], idx = 1, col[300005], val[300005];
vector <pii> a;
bool je[300005];
int tonumber(string s, int &x){
int ret = 0;
while(s[x] >= '0' && s[x] <= '9' && x < (int)s.size()){
ret = ret * 10 + s[x] - '0';
x++;
}
return ret;
}
int find(int x){
while(x != link[x]){
x = link[x];
}
return x;
}
bool same(int x, int y){
return (find(x) == find(y));
}
void unite(int x, int y){
x = find(x);
y = find(y);
if(sz[x] < sz[y]){
swap(x, y);
}
sz[x] += sz[y];
link[y] = x;
}
void dfs1(int x){
koja[x] = idx;
for(vector <int>::iterator i = fg[x].begin() ; i != fg[x].end() ; ++i){
int o = *i;
if(koja[o])
continue;
dfs1(o);
}
}
void dfs2(int x){
col[x] = 1;
for(vector <int>::iterator i = ms[x].begin() ; i != ms[x].end() ; ++i){
int o = *i;
if(col[o] == 2)
continue;
if(col[o] == 1){
je[koja[o]] = 1;
continue;
}
dfs2(o);
}
col[x] = 2;
topo[koja[x]].push_back(x);
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m >> v;
for(int i = 1 ; i <= m ; ++i){
link[i] = i;
sz[i] = 1;
}
for(int i = 0 ; i < v ; ++i){
string s;
cin >> s;
int sad = 0;
int x = tonumber(s, sad);
char c = s[sad];
sad++;
int y = tonumber(s, sad);
if(c == '<'){
a.push_back(mp(x, y));
}
else{
if(!same(x, y)){
unite(x, y);
}
}
}
for(int i = 0 ; i < (int)a.size() ; ++i){
int x = a[i].x, y = a[i].y;
x = find(x);
y = find(y);
ms[y].push_back(x);
fg[x].push_back(y);
fg[y].push_back(x);
}
for(int i = 1 ; i <= m ; ++i){
sort(ms[i].begin(), ms[i].end());
ms[i].resize(unique(ms[i].begin(), ms[i].end()) - ms[i].begin());
sort(fg[i].begin(), fg[i].end());
fg[i].resize(unique(fg[i].begin(), fg[i].end()) - fg[i].begin());
}
for(int i = 1 ; i <= m ; ++i){
int x = find(i);
if(koja[x])
continue;
dfs1(x);
idx++;
}
for(int i = 1 ; i <= m ; ++i){
int x = find(i);
if(col[x])
continue;
dfs2(x);
}
for(int i = 1 ; i < idx ; ++i){
reverse(topo[i].begin(), topo[i].end());
}
for(int i = 1 ; i <= m ; ++i){
val[i] = 1;
}
for(int i = 1 ; i < idx ; ++i){
int naj = 0;
for(int j = (int)topo[i].size() - 1 ; j >= 0 ; --j){
for(vector <int>::iterator v = ms[topo[i][j]].begin() ; v != ms[topo[i][j]].end() ; ++v){
int o = *v;
val[topo[i][j]] = max(val[topo[i][j]], val[o] + 1);
naj = max(naj, val[topo[i][j]]);
}
}
if(naj != n || je[i]){
for(int j = 0 ; j < (int)topo[i].size() ; ++j){
val[topo[i][j]] = -1;
}
}
}
for(int i = 1 ; i <= m ; ++i){
int x = find(i);
val[i] = val[x];
}
for(int i = 1 ; i <= m ; ++i){
if(val[i] == -1){
cout << "?" << endl;
}
else{
cout << "K" << val[i] << endl;
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
21632 KB |
Output is correct |
| 2 |
Correct |
26 ms |
21632 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
435 ms |
33596 KB |
Output is correct |
| 2 |
Correct |
446 ms |
33956 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
46 ms |
23664 KB |
Output is correct |
| 2 |
Correct |
48 ms |
23920 KB |
Output is correct |
| 3 |
Correct |
47 ms |
23920 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
874 ms |
42612 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
