| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 388253 |
2021-04-10T16:43:29 Z |
fammo |
KOVANICE (COI15_kovanice) |
C++11 |
|
514 ms |
46272 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 mn[N], 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; mn[b] = 0;
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){
if(deg[v] == (int)in[v].size() && !__m[v]){
q.push(v);
while(!q.empty()){
int v = q.front();
q.pop();
__m[v] =1;
for(auto u : adj[v]){
dp[u] = max(dp[u], dp[v] + 1), deg[u] ++;
if(deg[u] == (int)in[u].size() && !__m[u])q.push(u);
}
}
}
}
//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 ++)if(mn[i]){
if(!mark[i]){
pre(i);
dpcmp();
comp.clear(); tmp.clear();
}
}
return;
}
int32_t main(){
fastio;
///auto t = clock();
for(int i = 0; i < N; i ++)par[i] = i, mn[i] = 1;
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 |
22988 KB |
Output is correct |
| 2 |
Correct |
15 ms |
22964 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
161 ms |
32132 KB |
Output is correct |
| 2 |
Correct |
163 ms |
32604 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
35 ms |
25736 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
514 ms |
46272 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
