oj.uz

Submission #846255

# Submission time Handle Problem Language Result Execution time Memory
846255 2023-09-07T12:58:50 Z vjudge1 KOVANICE (COI15_kovanice) C++17
100 / 100
 195 ms 76992 KB 
#include <bits/stdc++.h>
#define int long long int
#define MP make_pair
#define pb push_back
#define REP(i,n) for(int (i) = 0; (i) < (n); (i)++)
using namespace std;

const double EPS = 0.00001;
const int INF = 1e9+500;
const int MOD = 1e9+7;
const int N = 6e5+5;
const int K = 1505;
const int ALPH = 26;
int n,m,q,v;
vector<vector<int> > adj;
vector<int> topo;
vector<int> nodes, is_rep;
vector<int> vis;
vector<int> depths;
vector<array<int,2> > dsrt;
vector<int> res;

void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

struct DSU {
    vector<int> p, sz;

    DSU(int num) {
        p.resize(num+1);
        sz.resize(num+1);
    }
    void make_set(int x) {
        p[x] = x;
        sz[x] = 1;
    }
    int find_set(int x) {
        if(p[x] == x) return x;
        return p[x] = find_set(p[x]);
    }
    void union_set(int x, int y) {
        x = find_set(x);
        y = find_set(y);
        if(x == y) return;
        if(sz[x] < sz[y]) swap(x,y);
        p[y] = x;
        sz[x] += sz[y];
    }

};
void dfs(int node) {
    vis[node] = 1;
    for(auto c : adj[node]) {
        if(vis[c]) continue;
        dfs(c);
    }
    topo.pb(node);

}

void topos() {
    vis.resize(N, 0); 
    for(auto i : nodes) {
        if(vis[i]) continue;
        dfs(i);
    }
    vis.resize(N, 0);
    reverse(topo.begin(), topo.end());
}

void find_depths() {
    for(auto i : topo) {
        depths[i] = max(depths[i] , 0ll);
        for(auto c : adj[i]) {
            
            depths[c] = max(depths[c] , depths[i] + 1);
        }
    }
    for(int i = 1; i<=m; i++) {
        if(depths[i] == -1) continue;
        dsrt.pb({depths[i], i});
    }
    sort(dsrt.begin(), dsrt.end());


}

vector<array<int,2> > eqs, ineqs;
void solve() {
    cin>>n>>m>>v;
    for(int i = 0; i<v; i++) {
        int a,b;
        char op;
        cin>>a;
        cin>>op;
        cin>>b;
        if(op == '<') {
            ineqs.pb({a,b});
        }   
        else if(op == '=') {
            eqs.pb({a,b});
        }
        else assert(0);
    }
    DSU ds(N);
    adj.resize(N);
    is_rep.resize(N, 0);
    for(int i = 1; i<=m; i++) {
        ds.make_set(i);
    }

    for(int i = 0; i<eqs.size(); i++) {
        ds.union_set(eqs[i][0], eqs[i][1]);
    }
    for(int i = 1; i<=m; i++) {
        is_rep[ds.find_set(i)] = 1;
    }
    for(int i = 1; i<=m; i++) {
        if(is_rep[i]) {
            nodes.pb(i);
        }
    }

    for(auto ind : ineqs) {
        adj[ds.find_set(ind[1])].pb(ds.find_set(ind[0]));
    }  
    
    topos();
    depths.resize(N, -1);
    find_depths();
    res.resize(N,0);

    for(int i = dsrt.size() - 1; i >= 0; i--) {
        if(dsrt[i][0] == n-1) {
            res[dsrt[i][1]] = n;
            continue;
        }
        for(auto c : adj[dsrt[i][1]]) {
            if(res[c] && dsrt[i][0] == depths[c] - 1) {
                res[dsrt[i][1]] = dsrt[i][0] + 1ll;
            }
        }

    }
    for(int i = 1; i<=m; i++) {
        int rep = ds.find_set(i);
        if(res[rep] == 0) {
            cout<<"?\n";
            continue;
        }
        cout<<"K"<<n - res[rep] + 1ll<<"\n";
    }

    

}   

signed main() {
    fastio();
    int test = 1;
    //cin>>test;
    while(test--) {
        solve();
    }
    
}

Compilation message

kovanice.cpp: In function 'void solve()':
kovanice.cpp:115:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |     for(int i = 0; i<eqs.size(); i++) {
      |                    ~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 42584 KB Output is correct
2 Correct 12 ms 42588 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 51512 KB Output is correct
2 Correct 72 ms 52780 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 45280 KB Output is correct
2 Correct 24 ms 45676 KB Output is correct
3 Correct 25 ms 45296 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 63156 KB Output is correct
2 Correct 154 ms 63784 KB Output is correct
3 Correct 141 ms 63412 KB Output is correct
4 Correct 180 ms 76992 KB Output is correct
5 Correct 195 ms 74876 KB Output is correct