| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 388256 |
2021-04-10T16:51:39 Z |
fammo |
KOVANICE (COI15_kovanice) |
C++11 |
|
713 ms |
56112 KB |
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
#define X first
#define Y second
#define pb push_back
#define fastio ios_base::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);
#define rndom mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define endl '\n'
//#define int long long
const int N = 300 * 1000 + 20;
int n, m, v, par[N], _rank[N], dp[N], deg[N];
vector<int>adj[N], comp, g[N], tmp, in[N];
vector<pii>qu;
bool mark[N], vis[N];
pair<char, pii> dcode(string s){
char c;
int pt= 0, x[2] = {0, 0};
for(int i = 0; i < (int)s.size(); i ++){
if(s[i] <= '9' && s[i] >= '0'){
x[pt] *= 10;
x[pt] += s[i] - '0';
}else{
c = s[i];
pt ++;
}
}
return {c, {x[0]-1, x[1]-1}};
}
int find(int a){
if(par[a] == a)return a;
return par[a] = find(par[a]);
}
void _union(int a, int b){
//cout << "UNI " << a << ' ' << b<< "OR ";
a = find(a), b = find(b);
//cout << a << ' ' << b << endl;
if(_rank[a] < _rank[b])swap(a, b);
par[b] = a;
if(_rank[a] == _rank[b]) _rank[a] ++;
return;
}
void pre(int v){
mark[v] = 1;
comp.pb(v);
for(auto u : g[v])if(!mark[u])pre(u);
return;
}
void dfs(int v){
vis[v] = 1;
for(auto u : adj[v]){
dp[u] = max(dp[u], dp[v] + 1);
if(!vis[u])dfs(u);
}
tmp.pb(v);
return;
}
bool _m[N], __m[N];
void path(int v){
//cout << "V:" << v << endl;
_m[v] = 1;
for(auto u : in[v]){
if(!_m[u] && dp[u] == dp[v] - 1){
path(u);
}
}return;
}
void dpcmp(){
queue<int>q;
for(auto i : comp){
if(!vis[i])dfs(i);
}
reverse(tmp.begin(), tmp.end());
for(int v : tmp){
for(auto u : adj[v]){
dp[u] = max(dp[u], dp[v] + 1);
}
}
//cout << "DP: ";
//for(int v:tmp)cout << dp[v] << ' ';
//cout << endl;
for(int i : tmp){
if(dp[i] == n - 1 && !_m[i]){
//cout << "PATH " << i << endl;
path(i);
// cout << endl;
}
}
for(int i : tmp){
dp[i] = (_m[i] ? dp[i] : -1);
}return;
}
void dfs_all(){
for(int i = 0; i < m; i ++){
int v = find(i);
if(!mark[v]){
pre(v);
dpcmp();
comp.clear(); tmp.clear();
}
}
return;
}
int32_t main(){
fastio;
///auto t = clock();
for(int i = 0; i < N; i ++)par[i] = i;
cin >> n >> m >> v;
for(int i = 0; i < v; i ++){
string s;
cin >> s;
auto p = dcode(s);
//cout << "DCODE : " << p.X << ' ' << p.Y.X << ' ' << p.Y.Y << endl;
if(p.X == '=') _union(p.Y.X, p.Y.Y);
else if(p.X == '<')qu.pb({p.Y.X, p.Y.Y});
else qu.pb({p.Y.Y, p.Y.X});
}
for(auto q : qu){
int x = q.X, y = q.Y;
x = find(x), y = find(y);
adj[x].pb(y);
in[y].pb(x);
g[x].pb(y); g[y].pb(x);
}
//for(int i = 0; i < m; i ++)if(mn[i])cout << i << ' ';
//cout << endl;
dfs_all();
for(int i = 0; i < m; i ++){
int p = find(i);
if(dp[p] == -1)cout << "?\n";
else cout << "K" << dp[p]+1 << endl;
}
///cout << clock() - t << "ms" << endl;
return 0;
}
Compilation message
kovanice.cpp: In function 'std::pair<char, std::pair<int, int> > dcode(std::string)':
kovanice.cpp:33:32: warning: 'c' may be used uninitialized in this function [-Wmaybe-uninitialized]
33 | return {c, {x[0]-1, x[1]-1}};
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
22732 KB |
Output is correct |
| 2 |
Correct |
14 ms |
22652 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
164 ms |
30840 KB |
Output is correct |
| 2 |
Correct |
186 ms |
31136 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
35 ms |
25412 KB |
Output is correct |
| 2 |
Correct |
36 ms |
25420 KB |
Output is correct |
| 3 |
Correct |
38 ms |
25644 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
510 ms |
44564 KB |
Output is correct |
| 2 |
Correct |
484 ms |
45112 KB |
Output is correct |
| 3 |
Correct |
518 ms |
45012 KB |
Output is correct |
| 4 |
Correct |
671 ms |
54924 KB |
Output is correct |
| 5 |
Correct |
713 ms |
56112 KB |
Output is correct |
