Submission #388256

#	Time	Username	Problem	Language	Result	Execution time	Memory
388256		fammo	KOVANICE (COI15_kovanice)	C++11	100 / 100	713 ms	56112 KiB

kovanice

#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 (stderr)

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 / 10
• Subtask 2: 40 / 40
• Subtask 3: 10 / 10
• Subtask 4: 40 / 40