oj.uz

Submission #1118863

# Submission time Handle Problem Language Result Execution time Memory
1118863 2024-11-26T10:15:17 Z yusufhocaoglu Swapping Cities (APIO20_swap) C++17
36 / 100
 250 ms 52916 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) {
    while (x>=dsu.size()) dsu.emplace_back();
    while (x>=parent.size()) parent.emplace_back();
    while (x>=sz.size()) sz.emplace_back();
    while (x>=cnt.size()) cnt.emplace_back();
    while (x>=weight.size()) weight.emplace_back();
    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) {
    make_set(s);
    edges[s] = {u,v};
    u = get_root(u);
    v = get_root(v);
    //cout<<"uniting "<<u<<" and "<<v<<" to "<<s<<endl;

    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+10);
    parent = vi(2*n+10);
    sz = vi(2*n+10);
    cnt = vi(2*n+10);
    adj = vector<vi>(2*n+10);
    weight = vi(2*n+10);

    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+2);
    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+5);
    chain = vp(2*n+5);
    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+5);
    dfs(s-1);
}

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

Compilation message

swap.cpp: In function 'void make_set(int)':
swap.cpp:26:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     while (x>=dsu.size()) dsu.emplace_back();
      |            ~^~~~~~~~~~~~
swap.cpp:27:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     while (x>=parent.size()) parent.emplace_back();
      |            ~^~~~~~~~~~~~~~~
swap.cpp:28:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     while (x>=sz.size()) sz.emplace_back();
      |            ~^~~~~~~~~~~
swap.cpp:29:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     while (x>=cnt.size()) cnt.emplace_back();
      |            ~^~~~~~~~~~~~
swap.cpp:30:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     while (x>=weight.size()) weight.emplace_back();
      |            ~^~~~~~~~~~~~~~~
swap.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
swap.cpp:202: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]
  202 |     for (int i = 0;i<ln2.size();i++) {
      |                    ~^~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 592 KB Output is correct
5 Correct 2 ms 760 KB Output is correct
6 Correct 1 ms 708 KB Output is correct
7 Correct 2 ms 592 KB Output is correct
8 Correct 2 ms 848 KB Output is correct
9 Correct 105 ms 30388 KB Output is correct
10 Correct 139 ms 36784 KB Output is correct
11 Correct 136 ms 36196 KB Output is correct
12 Correct 135 ms 38324 KB Output is correct
13 Correct 103 ms 43712 KB Output is correct
14 Correct 113 ms 30756 KB Output is correct
15 Correct 223 ms 40996 KB Output is correct
16 Correct 209 ms 39860 KB Output is correct
17 Correct 250 ms 42164 KB Output is correct
18 Correct 189 ms 47636 KB Output is correct
19 Correct 90 ms 11208 KB Output is correct
20 Correct 192 ms 41040 KB Output is correct
21 Correct 213 ms 39864 KB Output is correct
22 Correct 206 ms 42372 KB Output is correct
23 Correct 187 ms 48000 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 148 ms 50556 KB Output is correct
4 Correct 169 ms 52916 KB Output is correct
5 Correct 176 ms 51648 KB Output is correct
6 Correct 181 ms 52532 KB Output is correct
7 Correct 167 ms 52144 KB Output is correct
8 Correct 181 ms 50228 KB Output is correct
9 Correct 162 ms 51728 KB Output is correct
10 Correct 170 ms 49712 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 592 KB Output is correct
5 Correct 2 ms 760 KB Output is correct
6 Correct 1 ms 708 KB Output is correct
7 Correct 2 ms 592 KB Output is correct
8 Correct 2 ms 848 KB Output is correct
9 Correct 2 ms 336 KB Output is correct
10 Correct 2 ms 1016 KB Output is correct
11 Correct 2 ms 592 KB Output is correct
12 Correct 1 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 2 ms 848 KB Output is correct
16 Correct 1 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 2 ms 848 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 592 KB Output is correct
6 Correct 2 ms 760 KB Output is correct
7 Correct 1 ms 708 KB Output is correct
8 Correct 2 ms 592 KB Output is correct
9 Correct 2 ms 848 KB Output is correct
10 Correct 105 ms 30388 KB Output is correct
11 Correct 139 ms 36784 KB Output is correct
12 Correct 136 ms 36196 KB Output is correct
13 Correct 135 ms 38324 KB Output is correct
14 Correct 103 ms 43712 KB Output is correct
15 Correct 2 ms 1016 KB Output is correct
16 Correct 2 ms 592 KB Output is correct
17 Correct 1 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 2 ms 848 KB Output is correct
21 Correct 1 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 2 ms 848 KB Execution killed with signal 11
25 Halted 0 ms 0 KB -

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 592 KB Output is correct
5 Correct 2 ms 760 KB Output is correct
6 Correct 1 ms 708 KB Output is correct
7 Correct 2 ms 592 KB Output is correct
8 Correct 2 ms 848 KB Output is correct
9 Correct 105 ms 30388 KB Output is correct
10 Correct 139 ms 36784 KB Output is correct
11 Correct 136 ms 36196 KB Output is correct
12 Correct 135 ms 38324 KB Output is correct
13 Correct 103 ms 43712 KB Output is correct
14 Correct 113 ms 30756 KB Output is correct
15 Correct 223 ms 40996 KB Output is correct
16 Correct 209 ms 39860 KB Output is correct
17 Correct 250 ms 42164 KB Output is correct
18 Correct 189 ms 47636 KB Output is correct
19 Correct 148 ms 50556 KB Output is correct
20 Correct 169 ms 52916 KB Output is correct
21 Correct 176 ms 51648 KB Output is correct
22 Correct 181 ms 52532 KB Output is correct
23 Correct 167 ms 52144 KB Output is correct
24 Correct 181 ms 50228 KB Output is correct
25 Correct 162 ms 51728 KB Output is correct
26 Correct 170 ms 49712 KB Output is correct
27 Correct 2 ms 1016 KB Output is correct
28 Correct 2 ms 592 KB Output is correct
29 Correct 1 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 2 ms 848 KB Output is correct
33 Correct 1 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 12 ms 5688 KB Output is correct
37 Correct 147 ms 38064 KB Output is correct
38 Correct 154 ms 37936 KB Output is correct
39 Correct 142 ms 38068 KB Output is correct
40 Correct 127 ms 37512 KB Output is correct
41 Correct 161 ms 37380 KB Output is correct
42 Correct 124 ms 34484 KB Output is correct
43 Correct 136 ms 38428 KB Output is correct
44 Correct 137 ms 38068 KB Output is correct
45 Correct 118 ms 45244 KB Output is correct
46 Correct 148 ms 38324 KB Output is correct
47 Correct 23 ms 5540 KB Output is correct
48 Correct 236 ms 41908 KB Output is correct
49 Correct 202 ms 41908 KB Output is correct
50 Correct 233 ms 41908 KB Output is correct
51 Correct 227 ms 41656 KB Output is correct
52 Correct 215 ms 39348 KB Output is correct
53 Correct 163 ms 30364 KB Output is correct
54 Correct 238 ms 42476 KB Output is correct
55 Correct 246 ms 41908 KB Output is correct
56 Correct 186 ms 47560 KB Output is correct
57 Correct 226 ms 42628 KB Output is correct

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 592 KB Output is correct
6 Correct 2 ms 760 KB Output is correct
7 Correct 1 ms 708 KB Output is correct
8 Correct 2 ms 592 KB Output is correct
9 Correct 2 ms 848 KB Output is correct
10 Correct 105 ms 30388 KB Output is correct
11 Correct 139 ms 36784 KB Output is correct
12 Correct 136 ms 36196 KB Output is correct
13 Correct 135 ms 38324 KB Output is correct
14 Correct 103 ms 43712 KB Output is correct
15 Correct 113 ms 30756 KB Output is correct
16 Correct 223 ms 40996 KB Output is correct
17 Correct 209 ms 39860 KB Output is correct
18 Correct 250 ms 42164 KB Output is correct
19 Correct 189 ms 47636 KB Output is correct
20 Correct 148 ms 50556 KB Output is correct
21 Correct 169 ms 52916 KB Output is correct
22 Correct 176 ms 51648 KB Output is correct
23 Correct 181 ms 52532 KB Output is correct
24 Correct 167 ms 52144 KB Output is correct
25 Correct 181 ms 50228 KB Output is correct
26 Correct 162 ms 51728 KB Output is correct
27 Correct 170 ms 49712 KB Output is correct
28 Correct 2 ms 1016 KB Output is correct
29 Correct 2 ms 592 KB Output is correct
30 Correct 1 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 2 ms 848 KB Output is correct
34 Correct 1 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 12 ms 5688 KB Output is correct
38 Correct 147 ms 38064 KB Output is correct
39 Correct 154 ms 37936 KB Output is correct
40 Correct 142 ms 38068 KB Output is correct
41 Correct 127 ms 37512 KB Output is correct
42 Correct 161 ms 37380 KB Output is correct
43 Correct 124 ms 34484 KB Output is correct
44 Correct 136 ms 38428 KB Output is correct
45 Correct 137 ms 38068 KB Output is correct
46 Correct 118 ms 45244 KB Output is correct
47 Correct 148 ms 38324 KB Output is correct
48 Correct 23 ms 5540 KB Output is correct
49 Correct 236 ms 41908 KB Output is correct
50 Correct 202 ms 41908 KB Output is correct
51 Correct 233 ms 41908 KB Output is correct
52 Correct 227 ms 41656 KB Output is correct
53 Correct 215 ms 39348 KB Output is correct
54 Correct 163 ms 30364 KB Output is correct
55 Correct 238 ms 42476 KB Output is correct
56 Correct 246 ms 41908 KB Output is correct
57 Correct 186 ms 47560 KB Output is correct
58 Correct 226 ms 42628 KB Output is correct
59 Correct 90 ms 11208 KB Output is correct
60 Correct 192 ms 41040 KB Output is correct
61 Correct 213 ms 39864 KB Output is correct
62 Correct 206 ms 42372 KB Output is correct
63 Correct 187 ms 48000 KB Output is correct
64 Runtime error 2 ms 848 KB Execution killed with signal 11
65 Halted 0 ms 0 KB -