oj.uz

Submission #388254

# Submission time Handle Problem Language Result Execution time Memory
388254 2021-04-10T16:49:39 Z fammo KOVANICE (COI15_kovanice) C++11
100 / 100
 769 ms 57616 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){
        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 ++){
        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}};
      |                                ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 22732 KB Output is correct
2 Correct 17 ms 22656 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 31808 KB Output is correct
2 Correct 199 ms 32228 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 25400 KB Output is correct
2 Correct 38 ms 25504 KB Output is correct
3 Correct 41 ms 25700 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 555 ms 46016 KB Output is correct
2 Correct 567 ms 46652 KB Output is correct
3 Correct 529 ms 46424 KB Output is correct
4 Correct 709 ms 56328 KB Output is correct
5 Correct 769 ms 57616 KB Output is correct