oj.uz

Submission #1118847

# Submission time Handle Problem Language Result Execution time Memory
1118847 2024-11-26T08:58:35 Z yusufhocaoglu Swapping Cities (APIO20_swap) C++17
36 / 100
 281 ms 52920 KB 
#include "swap.h"

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define MOD2 998244353
#define ll long long
#define pri pair<int,int>
#define prl pair<ll,ll>
#define vi vector<int>
#define vl vector<ll>
#define vp vector<pair<int,int>>
#define vpl vector<pair<ll,ll>>
#define re return 0
#define sqrt sqrtl

vi dsu;
vi parent;
vi cnt;
vi sz;
vi weight;
vector<vi> adj;

void make_set(int x) {
    dsu[x] = x;
    parent[x] = x;
    sz[x] = 1;
    cnt[x] = 0;
    weight[x] = 0;
}

int get_root(int u) {
    if (dsu[u]==u) return u;
    return dsu[u] = get_root(dsu[u]);
}
int s;
vp edges;
void unite(int u,int v,int w) {
    edges[s] = {u,v};
    u = get_root(u);
    v = get_root(v);
    //cout<<"uniting "<<u<<" and "<<v<<" to "<<s<<endl;
    make_set(s);

    dsu[u] = dsu[v] = s;
    parent[u] = parent[v] = s;
    adj[s].push_back(u);
    weight[s] = w;
    if (u==v) sz[s]+=sz[u], cnt[s]+=cnt[u];
    else {
        sz[s]+=sz[u]+sz[v];
        cnt[s]+=cnt[u]+cnt[v];
        adj[s].push_back(v);
    }

    s++;
}

void tour(int u) {
    cout<<u<<" "<<weight[u]<<endl;
    for (auto m : adj[u]) {
        //cout<<"niggas gonna from "<<u<<" to "<<m<<endl;
        tour(m);
    }
}

vector<vi> adj_mst;

vi stf;
vp chain;

void dfs(int u) {
    if (chain[u].first==-1) stf[u] = u;
    else if (parent[u]!=u) stf[u] = stf[parent[u]];
    else stf[u] = -1;
    for (auto m : adj[u]) {
        dfs(m);
    }
}


pri cc(pri a,pri b,pri c) {
    //chain,chain,edge
    if (a.first == c.first && b.first == c.second) {
        return {a.second,b.second};
    } 
    if (a.second == c.first && b.first == c.second) {
        return {a.first,b.second};
    } 
    if (a.first == c.first && b.second == c.second) {
        return {a.second,b.first};
    } 
    if (a.second == c.first && b.second == c.second) {
        return {a.first,b.first};
    } 
    return {-1,-1};
}

vp ln2;
vp lnf;
vp seg2;
void dfs2(int u,int h) { // on the reachability tree
    lnf[u].first = ln2.size();
    ln2.push_back({h,u});
    for (auto v : adj[u]) {
        dfs2(v,h+1);
        ln2.push_back({h,u});
    }
    if (adj[u].size()==0) chain[u] = {u,u};
    else if (adj[u].size()==1) chain[u] = {-1,-1};
    else if (chain[adj[u][0]].first==-1 || chain[adj[u][1]].first==-1) chain[u]={-1,-1};
    else {
        //each child forms a chain
        //edge is edges[u].first - edges[u].second
        auto uc = chain[adj[u][0]];
        auto vc = chain[adj[u][1]];

        chain[u] = cc(uc,vc,edges[u]);

    }
    lnf[u].second = ln2.size()-1;
}

int lca2(int u,int v) {
    int l = min(lnf[u].first,lnf[v].first);
    int r = max(lnf[u].second,lnf[v].second);
    l+=ln2.size();
    r+=ln2.size();
    r++;
    pri ans = {1e9,1e9};
    for (;l<r;l>>=1,r>>=1) {
        if (l&1) {
            ans = min(ans,seg2[l++]);
        } if (r&1) {
            ans = min(ans,seg2[--r]);
        }
    }
    return ans.second;

}

int getMinimumFuelCapacity(int u,int v) {
    //pri lca1_ = lca(u,v);
    int lca2_ = lca2(u,v);
    //int path_len = node_l[fl[u].first].first+node_l[fl[v].first].first - lca1_.second*2; 
    if (chain[lca2_].first==-1) {
        return weight[lca2_];
    } else {
        //find earliest parent with no chain
        if (stf[lca2_]==-1) return -1;
        else return weight[stf[lca2_]];
    }
}

void init(int n,int m,vector<int> u,vector<int> v,vector<int> w) {
    dsu = vi(2*n+1);
    parent = vi(2*n+1);
    sz = vi(2*n+1);
    cnt = vi(2*n+1);
    adj = vector<vi>(2*n+1);
    weight = vi(2*n+1);

    s = n;

    struct edge {
        int u,v,w;
        bool operator<(const edge& other) const {
            return w<other.w;
        }
    };
    for (int i = 0;i<n;i++){
        make_set(i);
        cnt[i] = 1;
    }
    //cout<<"nigga"<<endl;
    vector<edge> ss;
    vector<edge> edging;
    for (int i = 0;i<m;i++) ss.push_back(edge{u[i],v[i],w[i]});
    sort(ss.begin(),ss.end());
    adj_mst = vector<vi>(n);
    edges = vp(2*n+1);
    for (auto edge : ss) {
        if (get_root(edge.u)!=get_root(edge.v)) {
            adj_mst[edge.u].push_back(edge.v);
            adj_mst[edge.v].push_back(edge.u);
        }
        unite(edge.u,edge.v,edge.w);
    }
    
    //cout<<cnt[s-1]<<endl;
    
    lnf = vp(2*n+1);
    chain = vp(2*n+1);
    dfs2(s-1,0);
    seg2 = vp(2*ln2.size()+2);
    for (int i = 0;i<ln2.size();i++) {
        seg2[i+ln2.size()] = ln2[i];
    }
    for (int i = ln2.size()-1;i>0;i--) {
        seg2[i] = min(seg2[2*i],seg2[2*i+1]);
    }
    stf = vi(2*n+1);
    dfs(s-1);
}

/*int32_t main() {
    int u[6] = {0,0,1,1,1,2};
    int v[6] = {1,2,2,3,4,3};
    int w[6] = {4,4,1,2,10,3};
    init(5, 6, u, v,w);
    cout<<getMinimumFuelCapacity(1,2)<<endl;
    return 0;
}*/

Compilation message

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

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 440 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 2 ms 764 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 2 ms 604 KB Output is correct
8 Correct 2 ms 860 KB Output is correct
9 Correct 113 ms 30268 KB Output is correct
10 Correct 142 ms 36800 KB Output is correct
11 Correct 159 ms 36212 KB Output is correct
12 Correct 174 ms 38336 KB Output is correct
13 Correct 108 ms 43824 KB Output is correct
14 Correct 136 ms 30652 KB Output is correct
15 Correct 256 ms 41048 KB Output is correct
16 Correct 259 ms 40024 KB Output is correct
17 Correct 238 ms 42192 KB Output is correct
18 Correct 202 ms 47676 KB Output is correct
19 Correct 80 ms 11164 KB Output is correct
20 Correct 219 ms 41248 KB Output is correct
21 Correct 253 ms 39980 KB Output is correct
22 Correct 281 ms 42396 KB Output is correct
23 Correct 194 ms 47988 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 440 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 242 ms 50472 KB Output is correct
4 Correct 170 ms 52920 KB Output is correct
5 Correct 162 ms 51428 KB Output is correct
6 Correct 164 ms 52664 KB Output is correct
7 Correct 186 ms 52156 KB Output is correct
8 Correct 222 ms 50276 KB Output is correct
9 Correct 167 ms 51800 KB Output is correct
10 Correct 173 ms 49708 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 440 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 2 ms 764 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 2 ms 604 KB Output is correct
8 Correct 2 ms 860 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 3 ms 848 KB Output is correct
11 Correct 3 ms 592 KB Output is correct
12 Correct 3 ms 592 KB Output is correct
13 Correct 2 ms 592 KB Output is correct
14 Correct 2 ms 592 KB Output is correct
15 Correct 3 ms 860 KB Output is correct
16 Correct 2 ms 592 KB Output is correct
17 Correct 2 ms 848 KB Output is correct
18 Correct 2 ms 592 KB Output is correct
19 Runtime error 3 ms 964 KB Execution killed with signal 6
20 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 440 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 2 ms 764 KB Output is correct
7 Correct 2 ms 604 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 2 ms 860 KB Output is correct
10 Correct 113 ms 30268 KB Output is correct
11 Correct 142 ms 36800 KB Output is correct
12 Correct 159 ms 36212 KB Output is correct
13 Correct 174 ms 38336 KB Output is correct
14 Correct 108 ms 43824 KB Output is correct
15 Correct 3 ms 848 KB Output is correct
16 Correct 3 ms 592 KB Output is correct
17 Correct 3 ms 592 KB Output is correct
18 Correct 2 ms 592 KB Output is correct
19 Correct 2 ms 592 KB Output is correct
20 Correct 3 ms 860 KB Output is correct
21 Correct 2 ms 592 KB Output is correct
22 Correct 2 ms 848 KB Output is correct
23 Correct 2 ms 592 KB Output is correct
24 Runtime error 3 ms 964 KB Execution killed with signal 6
25 Halted 0 ms 0 KB -

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 440 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 2 ms 764 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 2 ms 604 KB Output is correct
8 Correct 2 ms 860 KB Output is correct
9 Correct 113 ms 30268 KB Output is correct
10 Correct 142 ms 36800 KB Output is correct
11 Correct 159 ms 36212 KB Output is correct
12 Correct 174 ms 38336 KB Output is correct
13 Correct 108 ms 43824 KB Output is correct
14 Correct 136 ms 30652 KB Output is correct
15 Correct 256 ms 41048 KB Output is correct
16 Correct 259 ms 40024 KB Output is correct
17 Correct 238 ms 42192 KB Output is correct
18 Correct 202 ms 47676 KB Output is correct
19 Correct 242 ms 50472 KB Output is correct
20 Correct 170 ms 52920 KB Output is correct
21 Correct 162 ms 51428 KB Output is correct
22 Correct 164 ms 52664 KB Output is correct
23 Correct 186 ms 52156 KB Output is correct
24 Correct 222 ms 50276 KB Output is correct
25 Correct 167 ms 51800 KB Output is correct
26 Correct 173 ms 49708 KB Output is correct
27 Correct 3 ms 848 KB Output is correct
28 Correct 3 ms 592 KB Output is correct
29 Correct 3 ms 592 KB Output is correct
30 Correct 2 ms 592 KB Output is correct
31 Correct 2 ms 592 KB Output is correct
32 Correct 3 ms 860 KB Output is correct
33 Correct 2 ms 592 KB Output is correct
34 Correct 2 ms 848 KB Output is correct
35 Correct 2 ms 592 KB Output is correct
36 Correct 18 ms 5516 KB Output is correct
37 Correct 169 ms 38068 KB Output is correct
38 Correct 152 ms 38068 KB Output is correct
39 Correct 178 ms 38080 KB Output is correct
40 Correct 159 ms 37556 KB Output is correct
41 Correct 127 ms 37300 KB Output is correct
42 Correct 164 ms 34484 KB Output is correct
43 Correct 151 ms 38328 KB Output is correct
44 Correct 149 ms 38048 KB Output is correct
45 Correct 92 ms 45224 KB Output is correct
46 Correct 135 ms 38440 KB Output is correct
47 Correct 19 ms 5360 KB Output is correct
48 Correct 219 ms 41928 KB Output is correct
49 Correct 222 ms 42020 KB Output is correct
50 Correct 212 ms 41764 KB Output is correct
51 Correct 204 ms 41752 KB Output is correct
52 Correct 199 ms 39452 KB Output is correct
53 Correct 248 ms 30624 KB Output is correct
54 Correct 248 ms 42356 KB Output is correct
55 Correct 271 ms 41892 KB Output is correct
56 Correct 196 ms 47544 KB Output is correct
57 Correct 244 ms 42484 KB Output is correct

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 440 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 2 ms 764 KB Output is correct
7 Correct 2 ms 604 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 2 ms 860 KB Output is correct
10 Correct 113 ms 30268 KB Output is correct
11 Correct 142 ms 36800 KB Output is correct
12 Correct 159 ms 36212 KB Output is correct
13 Correct 174 ms 38336 KB Output is correct
14 Correct 108 ms 43824 KB Output is correct
15 Correct 136 ms 30652 KB Output is correct
16 Correct 256 ms 41048 KB Output is correct
17 Correct 259 ms 40024 KB Output is correct
18 Correct 238 ms 42192 KB Output is correct
19 Correct 202 ms 47676 KB Output is correct
20 Correct 242 ms 50472 KB Output is correct
21 Correct 170 ms 52920 KB Output is correct
22 Correct 162 ms 51428 KB Output is correct
23 Correct 164 ms 52664 KB Output is correct
24 Correct 186 ms 52156 KB Output is correct
25 Correct 222 ms 50276 KB Output is correct
26 Correct 167 ms 51800 KB Output is correct
27 Correct 173 ms 49708 KB Output is correct
28 Correct 3 ms 848 KB Output is correct
29 Correct 3 ms 592 KB Output is correct
30 Correct 3 ms 592 KB Output is correct
31 Correct 2 ms 592 KB Output is correct
32 Correct 2 ms 592 KB Output is correct
33 Correct 3 ms 860 KB Output is correct
34 Correct 2 ms 592 KB Output is correct
35 Correct 2 ms 848 KB Output is correct
36 Correct 2 ms 592 KB Output is correct
37 Correct 18 ms 5516 KB Output is correct
38 Correct 169 ms 38068 KB Output is correct
39 Correct 152 ms 38068 KB Output is correct
40 Correct 178 ms 38080 KB Output is correct
41 Correct 159 ms 37556 KB Output is correct
42 Correct 127 ms 37300 KB Output is correct
43 Correct 164 ms 34484 KB Output is correct
44 Correct 151 ms 38328 KB Output is correct
45 Correct 149 ms 38048 KB Output is correct
46 Correct 92 ms 45224 KB Output is correct
47 Correct 135 ms 38440 KB Output is correct
48 Correct 19 ms 5360 KB Output is correct
49 Correct 219 ms 41928 KB Output is correct
50 Correct 222 ms 42020 KB Output is correct
51 Correct 212 ms 41764 KB Output is correct
52 Correct 204 ms 41752 KB Output is correct
53 Correct 199 ms 39452 KB Output is correct
54 Correct 248 ms 30624 KB Output is correct
55 Correct 248 ms 42356 KB Output is correct
56 Correct 271 ms 41892 KB Output is correct
57 Correct 196 ms 47544 KB Output is correct
58 Correct 244 ms 42484 KB Output is correct
59 Correct 80 ms 11164 KB Output is correct
60 Correct 219 ms 41248 KB Output is correct
61 Correct 253 ms 39980 KB Output is correct
62 Correct 281 ms 42396 KB Output is correct
63 Correct 194 ms 47988 KB Output is correct
64 Runtime error 3 ms 964 KB Execution killed with signal 6
65 Halted 0 ms 0 KB -