oj.uz

Submission #571110

# Submission time Handle Problem Language Result Execution time Memory
571110 2022-06-01T09:28:08 Z MadokaMagicaFan Swapping Cities (APIO20_swap) C++14
100 / 100
 448 ms 68456 KB 
#include "bits/stdc++.h"

using namespace std;

using ll = long long;
const ll inf = 1e9;
const int md1 = 1e9+7;
const int md2 = 998244353;

#define all(v)                      v.begin(), v.end()
#define rall(v)                     v.rbegin(), v.rend()
#define sz(v)                       ((int)v.size())

#define forn(i,n)                   for(int i = 0; i < n; ++i)
#define forbe(i,b,e)                for(int i = b; i < e; ++i)

#define pb                          push_back

#define pry                         puts("YES")
#define prn                         puts("NO")
#define endl                        '\n'

#define fst                         first
#define scn                         second

const int N = 1e5;
const int M = 2e5;

struct node{
    int w;
    bool c;
    int p;
    int d;
    vector<int> child;
    int jump[30];
};

node ns[N+M];

int par[N+M];
int deg[N];

int
getpar(int x)
{
    return par[x] = (x == par[x]) ? x : getpar(par[x]);
}

void
dfs(int x, int d)
{
    ns[x].d = d;
    for (int i = 0; i < sz(ns[x].child); ++i) {
        ns[ns[x].child[i]].p = x;
        ns[ns[x].child[i]].d = d+1;
        if (ns[ns[x].child[i]].c) {
            dfs(ns[x].child[i], d+1);
        } else {
            for (auto u : ns[ns[x].child[i]].child){
                ns[x].child.pb(u);
            }
        }
    }
    return;
}


void
init(int n, int m, vector<int> u, vector<int> v, vector<int> w)
{
    for (int i = 0; i < n+m; ++i) {
        par[i] = i;
        ns[i].c = 0;
    }

    for (int i = 0; i < n; ++i) {
        ns[i].w = 0;
        ns[i].c = 1;
    }

    vector<pair<int,int>> edg;

    for (int i = 0; i < m; ++i) {
        edg.pb({w[i],i});
    }

    sort(edg.begin(), edg.end());

    int root = 0;
    for (int i = 0; i < m; ++i) {
        int x = edg[i].scn;
        ++deg[u[x]];
        ++deg[v[x]];

        if (getpar(u[x]) == getpar(v[x])) {
            if (ns[getpar(u[x])].c == 0) {
                ns[getpar(u[x])].c = 1;
                ns[getpar(u[x])].w = edg[i].fst;
            }
            continue;
        }

        ns[n+i].w = edg[i].fst;
        ns[n+i].child.pb(getpar(u[x]));
        ns[n+i].child.pb(getpar(v[x]));
        ns[n+i].c = 0;
        root = n+i;
        if (deg[u[x]] > 2 || deg[v[x]] > 2) ns[n+i].c = 1;
        if (ns[getpar(u[x])].c && getpar(u[x]) >= n) ns[n+i].c = 1;
        if (ns[getpar(v[x])].c && getpar(v[x]) >= n) ns[n+i].c = 1;
        par[getpar(u[x])] = n+i;
        par[getpar(v[x])] = n+i;
    }

    ns[root].p = root;

    dfs(root,0);

    for (int i = 0; i < n+m; ++i) {
        ns[i].jump[0] = ns[i].p;
    }

    for (int j = 1; j < 30; ++j) {
        for (int i = 0; i < n+m; ++i) {
            ns[i].jump[j] = ns[ns[i].jump[j-1]].jump[j-1];
        }
    }

    return;
}

int
getMinimumFuelCapacity(int x, int y)
{
    while (ns[x].d > ns[y].d) x = ns[x].jump[31-__builtin_clz(ns[x].d-ns[y].d)];
    while (ns[y].d > ns[x].d) y = ns[y].jump[31-__builtin_clz(ns[y].d-ns[x].d)];
    assert(x!=y);

    while (ns[x].p != ns[y].p) {
        for (int j = 0; j < 30; ++j) {
            if (ns[x].jump[j] == ns[y].jump[j]) {
                x = ns[x].jump[j-1];
                y = ns[y].jump[j-1];
                break;
            }
        }
    }

    x = ns[x].p;
    if (!ns[x].c)
        return -1;
    return ns[x].w;
}

#ifdef ONPC
void
solve()
{
    int n,m ;
    cin >> n >> m;
    vector<int> u(m);
    vector<int> v(m);
    vector<int> w(m);

    for (int i = 0; i < m; ++i) {
        cin >> u[i];
    }
    for (int i = 0; i < m; ++i) {
        cin >> v[i];
    }
    for (int i = 0; i < m; ++i) {
        cin >> w[i];
    }

    init(n,m,u,v,w);

    int q;
    cin >> q;
    while (q--) {
        cin >> n >> m;
        cout << getMinimumFuelCapacity(n,m) << endl;
    }
}

int32_t
main()
{
    /* ios_base::sync_with_stdio(0);cin.tie(0); */
    freopen("in", "r", stdin);
    int t = 1;
    cin >> t;
    while(t--)
        solve();
}
#endif

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 47188 KB Output is correct
2 Correct 25 ms 47224 KB Output is correct
3 Correct 20 ms 47268 KB Output is correct
4 Correct 25 ms 47292 KB Output is correct
5 Correct 22 ms 47316 KB Output is correct
6 Correct 19 ms 47308 KB Output is correct
7 Correct 19 ms 47348 KB Output is correct
8 Correct 20 ms 47344 KB Output is correct
9 Correct 143 ms 55384 KB Output is correct
10 Correct 171 ms 56700 KB Output is correct
11 Correct 160 ms 56584 KB Output is correct
12 Correct 181 ms 56948 KB Output is correct
13 Correct 170 ms 57596 KB Output is correct
14 Correct 137 ms 55504 KB Output is correct
15 Correct 206 ms 58276 KB Output is correct
16 Correct 228 ms 58036 KB Output is correct
17 Correct 232 ms 58492 KB Output is correct
18 Correct 211 ms 59116 KB Output is correct
19 Correct 83 ms 52784 KB Output is correct
20 Correct 230 ms 58180 KB Output is correct
21 Correct 214 ms 58228 KB Output is correct
22 Correct 276 ms 58592 KB Output is correct
23 Correct 218 ms 59156 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 47188 KB Output is correct
2 Correct 25 ms 47224 KB Output is correct
3 Correct 363 ms 67616 KB Output is correct
4 Correct 350 ms 68456 KB Output is correct
5 Correct 380 ms 68124 KB Output is correct
6 Correct 376 ms 68312 KB Output is correct
7 Correct 359 ms 68316 KB Output is correct
8 Correct 351 ms 67620 KB Output is correct
9 Correct 389 ms 68200 KB Output is correct
10 Correct 338 ms 67484 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 47188 KB Output is correct
2 Correct 25 ms 47224 KB Output is correct
3 Correct 20 ms 47268 KB Output is correct
4 Correct 25 ms 47292 KB Output is correct
5 Correct 22 ms 47316 KB Output is correct
6 Correct 19 ms 47308 KB Output is correct
7 Correct 19 ms 47348 KB Output is correct
8 Correct 20 ms 47344 KB Output is correct
9 Correct 22 ms 47260 KB Output is correct
10 Correct 31 ms 47268 KB Output is correct
11 Correct 22 ms 47320 KB Output is correct
12 Correct 21 ms 47308 KB Output is correct
13 Correct 20 ms 47264 KB Output is correct
14 Correct 24 ms 47280 KB Output is correct
15 Correct 22 ms 47324 KB Output is correct
16 Correct 22 ms 47424 KB Output is correct
17 Correct 20 ms 47320 KB Output is correct
18 Correct 21 ms 47276 KB Output is correct
19 Correct 20 ms 47316 KB Output is correct
20 Correct 21 ms 47300 KB Output is correct
21 Correct 24 ms 47476 KB Output is correct
22 Correct 25 ms 47284 KB Output is correct
23 Correct 25 ms 47308 KB Output is correct
24 Correct 21 ms 47316 KB Output is correct
25 Correct 22 ms 47316 KB Output is correct
26 Correct 22 ms 47316 KB Output is correct
27 Correct 20 ms 47400 KB Output is correct
28 Correct 21 ms 47420 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47260 KB Output is correct
2 Correct 19 ms 47188 KB Output is correct
3 Correct 25 ms 47224 KB Output is correct
4 Correct 20 ms 47268 KB Output is correct
5 Correct 25 ms 47292 KB Output is correct
6 Correct 22 ms 47316 KB Output is correct
7 Correct 19 ms 47308 KB Output is correct
8 Correct 19 ms 47348 KB Output is correct
9 Correct 20 ms 47344 KB Output is correct
10 Correct 143 ms 55384 KB Output is correct
11 Correct 171 ms 56700 KB Output is correct
12 Correct 160 ms 56584 KB Output is correct
13 Correct 181 ms 56948 KB Output is correct
14 Correct 170 ms 57596 KB Output is correct
15 Correct 31 ms 47268 KB Output is correct
16 Correct 22 ms 47320 KB Output is correct
17 Correct 21 ms 47308 KB Output is correct
18 Correct 20 ms 47264 KB Output is correct
19 Correct 24 ms 47280 KB Output is correct
20 Correct 22 ms 47324 KB Output is correct
21 Correct 22 ms 47424 KB Output is correct
22 Correct 20 ms 47320 KB Output is correct
23 Correct 21 ms 47276 KB Output is correct
24 Correct 20 ms 47316 KB Output is correct
25 Correct 21 ms 47300 KB Output is correct
26 Correct 24 ms 47476 KB Output is correct
27 Correct 25 ms 47284 KB Output is correct
28 Correct 25 ms 47308 KB Output is correct
29 Correct 21 ms 47316 KB Output is correct
30 Correct 22 ms 47316 KB Output is correct
31 Correct 22 ms 47316 KB Output is correct
32 Correct 20 ms 47400 KB Output is correct
33 Correct 21 ms 47420 KB Output is correct
34 Correct 33 ms 48564 KB Output is correct
35 Correct 165 ms 56372 KB Output is correct
36 Correct 166 ms 56428 KB Output is correct
37 Correct 173 ms 56592 KB Output is correct
38 Correct 177 ms 56424 KB Output is correct
39 Correct 185 ms 56468 KB Output is correct
40 Correct 172 ms 55540 KB Output is correct
41 Correct 174 ms 56884 KB Output is correct
42 Correct 191 ms 56932 KB Output is correct
43 Correct 174 ms 62784 KB Output is correct
44 Correct 219 ms 56220 KB Output is correct
45 Correct 218 ms 59512 KB Output is correct
46 Correct 166 ms 56496 KB Output is correct
47 Correct 182 ms 56608 KB Output is correct
48 Correct 186 ms 59124 KB Output is correct
49 Correct 146 ms 54568 KB Output is correct
50 Correct 124 ms 52840 KB Output is correct
51 Correct 205 ms 57668 KB Output is correct
52 Correct 223 ms 58812 KB Output is correct
53 Correct 284 ms 59508 KB Output is correct
54 Correct 268 ms 60220 KB Output is correct
55 Correct 181 ms 61880 KB Output is correct
56 Correct 309 ms 61884 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 47188 KB Output is correct
2 Correct 25 ms 47224 KB Output is correct
3 Correct 20 ms 47268 KB Output is correct
4 Correct 25 ms 47292 KB Output is correct
5 Correct 22 ms 47316 KB Output is correct
6 Correct 19 ms 47308 KB Output is correct
7 Correct 19 ms 47348 KB Output is correct
8 Correct 20 ms 47344 KB Output is correct
9 Correct 143 ms 55384 KB Output is correct
10 Correct 171 ms 56700 KB Output is correct
11 Correct 160 ms 56584 KB Output is correct
12 Correct 181 ms 56948 KB Output is correct
13 Correct 170 ms 57596 KB Output is correct
14 Correct 137 ms 55504 KB Output is correct
15 Correct 206 ms 58276 KB Output is correct
16 Correct 228 ms 58036 KB Output is correct
17 Correct 232 ms 58492 KB Output is correct
18 Correct 211 ms 59116 KB Output is correct
19 Correct 363 ms 67616 KB Output is correct
20 Correct 350 ms 68456 KB Output is correct
21 Correct 380 ms 68124 KB Output is correct
22 Correct 376 ms 68312 KB Output is correct
23 Correct 359 ms 68316 KB Output is correct
24 Correct 351 ms 67620 KB Output is correct
25 Correct 389 ms 68200 KB Output is correct
26 Correct 338 ms 67484 KB Output is correct
27 Correct 31 ms 47268 KB Output is correct
28 Correct 22 ms 47320 KB Output is correct
29 Correct 21 ms 47308 KB Output is correct
30 Correct 20 ms 47264 KB Output is correct
31 Correct 24 ms 47280 KB Output is correct
32 Correct 22 ms 47324 KB Output is correct
33 Correct 22 ms 47424 KB Output is correct
34 Correct 20 ms 47320 KB Output is correct
35 Correct 21 ms 47276 KB Output is correct
36 Correct 33 ms 48564 KB Output is correct
37 Correct 165 ms 56372 KB Output is correct
38 Correct 166 ms 56428 KB Output is correct
39 Correct 173 ms 56592 KB Output is correct
40 Correct 177 ms 56424 KB Output is correct
41 Correct 185 ms 56468 KB Output is correct
42 Correct 172 ms 55540 KB Output is correct
43 Correct 174 ms 56884 KB Output is correct
44 Correct 191 ms 56932 KB Output is correct
45 Correct 174 ms 62784 KB Output is correct
46 Correct 219 ms 56220 KB Output is correct
47 Correct 42 ms 48948 KB Output is correct
48 Correct 252 ms 58692 KB Output is correct
49 Correct 250 ms 58228 KB Output is correct
50 Correct 247 ms 58300 KB Output is correct
51 Correct 266 ms 58252 KB Output is correct
52 Correct 257 ms 57920 KB Output is correct
53 Correct 230 ms 56604 KB Output is correct
54 Correct 238 ms 58968 KB Output is correct
55 Correct 250 ms 58488 KB Output is correct
56 Correct 401 ms 62812 KB Output is correct
57 Correct 284 ms 58732 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47260 KB Output is correct
2 Correct 19 ms 47188 KB Output is correct
3 Correct 25 ms 47224 KB Output is correct
4 Correct 20 ms 47268 KB Output is correct
5 Correct 25 ms 47292 KB Output is correct
6 Correct 22 ms 47316 KB Output is correct
7 Correct 19 ms 47308 KB Output is correct
8 Correct 19 ms 47348 KB Output is correct
9 Correct 20 ms 47344 KB Output is correct
10 Correct 143 ms 55384 KB Output is correct
11 Correct 171 ms 56700 KB Output is correct
12 Correct 160 ms 56584 KB Output is correct
13 Correct 181 ms 56948 KB Output is correct
14 Correct 170 ms 57596 KB Output is correct
15 Correct 137 ms 55504 KB Output is correct
16 Correct 206 ms 58276 KB Output is correct
17 Correct 228 ms 58036 KB Output is correct
18 Correct 232 ms 58492 KB Output is correct
19 Correct 211 ms 59116 KB Output is correct
20 Correct 363 ms 67616 KB Output is correct
21 Correct 350 ms 68456 KB Output is correct
22 Correct 380 ms 68124 KB Output is correct
23 Correct 376 ms 68312 KB Output is correct
24 Correct 359 ms 68316 KB Output is correct
25 Correct 351 ms 67620 KB Output is correct
26 Correct 389 ms 68200 KB Output is correct
27 Correct 338 ms 67484 KB Output is correct
28 Correct 31 ms 47268 KB Output is correct
29 Correct 22 ms 47320 KB Output is correct
30 Correct 21 ms 47308 KB Output is correct
31 Correct 20 ms 47264 KB Output is correct
32 Correct 24 ms 47280 KB Output is correct
33 Correct 22 ms 47324 KB Output is correct
34 Correct 22 ms 47424 KB Output is correct
35 Correct 20 ms 47320 KB Output is correct
36 Correct 21 ms 47276 KB Output is correct
37 Correct 33 ms 48564 KB Output is correct
38 Correct 165 ms 56372 KB Output is correct
39 Correct 166 ms 56428 KB Output is correct
40 Correct 173 ms 56592 KB Output is correct
41 Correct 177 ms 56424 KB Output is correct
42 Correct 185 ms 56468 KB Output is correct
43 Correct 172 ms 55540 KB Output is correct
44 Correct 174 ms 56884 KB Output is correct
45 Correct 191 ms 56932 KB Output is correct
46 Correct 174 ms 62784 KB Output is correct
47 Correct 219 ms 56220 KB Output is correct
48 Correct 42 ms 48948 KB Output is correct
49 Correct 252 ms 58692 KB Output is correct
50 Correct 250 ms 58228 KB Output is correct
51 Correct 247 ms 58300 KB Output is correct
52 Correct 266 ms 58252 KB Output is correct
53 Correct 257 ms 57920 KB Output is correct
54 Correct 230 ms 56604 KB Output is correct
55 Correct 238 ms 58968 KB Output is correct
56 Correct 250 ms 58488 KB Output is correct
57 Correct 401 ms 62812 KB Output is correct
58 Correct 284 ms 58732 KB Output is correct
59 Correct 83 ms 52784 KB Output is correct
60 Correct 230 ms 58180 KB Output is correct
61 Correct 214 ms 58228 KB Output is correct
62 Correct 276 ms 58592 KB Output is correct
63 Correct 218 ms 59156 KB Output is correct
64 Correct 20 ms 47316 KB Output is correct
65 Correct 21 ms 47300 KB Output is correct
66 Correct 24 ms 47476 KB Output is correct
67 Correct 25 ms 47284 KB Output is correct
68 Correct 25 ms 47308 KB Output is correct
69 Correct 21 ms 47316 KB Output is correct
70 Correct 22 ms 47316 KB Output is correct
71 Correct 22 ms 47316 KB Output is correct
72 Correct 20 ms 47400 KB Output is correct
73 Correct 21 ms 47420 KB Output is correct
74 Correct 218 ms 59512 KB Output is correct
75 Correct 166 ms 56496 KB Output is correct
76 Correct 182 ms 56608 KB Output is correct
77 Correct 186 ms 59124 KB Output is correct
78 Correct 146 ms 54568 KB Output is correct
79 Correct 124 ms 52840 KB Output is correct
80 Correct 205 ms 57668 KB Output is correct
81 Correct 223 ms 58812 KB Output is correct
82 Correct 284 ms 59508 KB Output is correct
83 Correct 268 ms 60220 KB Output is correct
84 Correct 181 ms 61880 KB Output is correct
85 Correct 309 ms 61884 KB Output is correct
86 Correct 120 ms 52608 KB Output is correct
87 Correct 262 ms 58392 KB Output is correct
88 Correct 264 ms 58328 KB Output is correct
89 Correct 352 ms 60352 KB Output is correct
90 Correct 252 ms 56476 KB Output is correct
91 Correct 233 ms 55908 KB Output is correct
92 Correct 305 ms 59384 KB Output is correct
93 Correct 301 ms 60032 KB Output is correct
94 Correct 448 ms 61380 KB Output is correct
95 Correct 366 ms 61848 KB Output is correct
96 Correct 433 ms 63356 KB Output is correct
97 Correct 427 ms 62164 KB Output is correct