oj.uz

Submission #571185

# Submission time Handle Problem Language Result Execution time Memory
571185 2022-06-01T12:10:20 Z 2fat2code Swapping Cities (APIO20_swap) C++17
13 / 100
 251 ms 43016 KB 
#include "swap.h"
#include <bits/stdc++.h>
#define fr first
#define sc second
#define all(s) s.begin(), s.end()
using namespace std;

const int nmax = 300005;

int pardsu[nmax], last, lca[nmax][20], marked[nmax], grad[nmax], val[nmax], timp, in[nmax], out[nmax], apropiat[nmax];
vector<pair<int, pair<int,int>>>edges;
vector<int>nod[nmax];

int findpar(int x){
    if(x != pardsu[x]){
        pardsu[x] = findpar(pardsu[x]);
    }
    return pardsu[x];
}

void dfs(int s, int apr = 0, int par = 0){
    in[s] = ++timp;
    if(marked[s]) apr = s;
    apropiat[s] = apr;
    for(auto it : nod[s]){
        if(it != par){
            dfs(it, apr, s);
        }
    }
    out[s] = ++timp;
}

bool is_lca(int x, int y){
    if(in[x] <= in[y] && out[x] >= out[y]) return true;
    else return false;
}

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
    last = N;
    for(int i=1;i<=N;i++) pardsu[i] = i;
    for(int i=0;i<M;i++){
        U[i]++; V[i]++;
        edges.push_back({W[i], {U[i], V[i]}});
    }
    sort(all(edges));
    for(auto it : edges){
        int x = findpar(it.sc.fr);
        int y = findpar(it.sc.sc);
        ++last;
        pardsu[y] = last;
        pardsu[x] = last;
        pardsu[last] = last;
        val[last] = it.fr;
        grad[it.sc.sc]++;
        grad[it.sc.fr]++;
        lca[x][0] = last;
        lca[y][0] = last;
        nod[last].push_back(x);
        if(x != y) nod[last].push_back(y);
        if(x == y){
            marked[last] = 1;
        }
        else{
            if(grad[it.sc.sc] >= 3 || grad[it.sc.fr] >= 3){
                marked[last] = 1;
            }
        }
    }
    for(int i=1;i<=19;i++){
        for(int j=1;j<=last;j++){
            lca[j][i] = lca[lca[j][i-1]][i-1];
        }
    }
    dfs(last);
   // assert(last == N + M);
}

int getMinimumFuelCapacity(int X, int Y) {
    X++;
    Y++;
    int curr;
    if(is_lca(X, Y)) curr = X;
    else if(is_lca(Y, X)) curr = Y;
    else{
        curr = X;
        for(int i=19;i>=0;i--){
            if(lca[curr][i] != 0 && !is_lca(lca[curr][i], Y)) curr = lca[curr][i];
        }
        curr = lca[curr][0];
    }
    if(!apropiat[curr]) return -1;
    else{
        return val[apropiat[curr]];
    }
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 3 ms 7380 KB Output is correct
4 Correct 4 ms 7380 KB Output is correct
5 Correct 4 ms 7508 KB Output is correct
6 Correct 5 ms 7524 KB Output is correct
7 Correct 5 ms 7636 KB Output is correct
8 Correct 4 ms 7636 KB Output is correct
9 Correct 85 ms 27968 KB Output is correct
10 Correct 112 ms 32448 KB Output is correct
11 Correct 106 ms 32052 KB Output is correct
12 Correct 110 ms 33512 KB Output is correct
13 Correct 121 ms 36800 KB Output is correct
14 Correct 91 ms 28000 KB Output is correct
15 Correct 177 ms 34496 KB Output is correct
16 Correct 170 ms 33776 KB Output is correct
17 Correct 178 ms 35288 KB Output is correct
18 Correct 241 ms 38484 KB Output is correct
19 Correct 70 ms 14992 KB Output is correct
20 Correct 175 ms 35760 KB Output is correct
21 Correct 174 ms 35076 KB Output is correct
22 Correct 192 ms 36764 KB Output is correct
23 Correct 238 ms 39848 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 244 ms 41516 KB Output is correct
4 Correct 236 ms 43016 KB Output is correct
5 Correct 251 ms 42188 KB Output is correct
6 Correct 239 ms 42784 KB Output is correct
7 Correct 251 ms 42604 KB Output is correct
8 Correct 242 ms 41224 KB Output is correct
9 Correct 249 ms 42304 KB Output is correct
10 Correct 236 ms 40884 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 3 ms 7380 KB Output is correct
4 Correct 4 ms 7380 KB Output is correct
5 Correct 4 ms 7508 KB Output is correct
6 Correct 5 ms 7524 KB Output is correct
7 Correct 5 ms 7636 KB Output is correct
8 Correct 4 ms 7636 KB Output is correct
9 Correct 4 ms 7380 KB Output is correct
10 Correct 4 ms 7636 KB Output is correct
11 Incorrect 4 ms 7636 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 3 ms 7380 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 3 ms 7380 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 4 ms 7508 KB Output is correct
7 Correct 5 ms 7524 KB Output is correct
8 Correct 5 ms 7636 KB Output is correct
9 Correct 4 ms 7636 KB Output is correct
10 Correct 85 ms 27968 KB Output is correct
11 Correct 112 ms 32448 KB Output is correct
12 Correct 106 ms 32052 KB Output is correct
13 Correct 110 ms 33512 KB Output is correct
14 Correct 121 ms 36800 KB Output is correct
15 Correct 4 ms 7636 KB Output is correct
16 Incorrect 4 ms 7636 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 3 ms 7380 KB Output is correct
4 Correct 4 ms 7380 KB Output is correct
5 Correct 4 ms 7508 KB Output is correct
6 Correct 5 ms 7524 KB Output is correct
7 Correct 5 ms 7636 KB Output is correct
8 Correct 4 ms 7636 KB Output is correct
9 Correct 85 ms 27968 KB Output is correct
10 Correct 112 ms 32448 KB Output is correct
11 Correct 106 ms 32052 KB Output is correct
12 Correct 110 ms 33512 KB Output is correct
13 Correct 121 ms 36800 KB Output is correct
14 Correct 91 ms 28000 KB Output is correct
15 Correct 177 ms 34496 KB Output is correct
16 Correct 170 ms 33776 KB Output is correct
17 Correct 178 ms 35288 KB Output is correct
18 Correct 241 ms 38484 KB Output is correct
19 Correct 244 ms 41516 KB Output is correct
20 Correct 236 ms 43016 KB Output is correct
21 Correct 251 ms 42188 KB Output is correct
22 Correct 239 ms 42784 KB Output is correct
23 Correct 251 ms 42604 KB Output is correct
24 Correct 242 ms 41224 KB Output is correct
25 Correct 249 ms 42304 KB Output is correct
26 Correct 236 ms 40884 KB Output is correct
27 Correct 4 ms 7636 KB Output is correct
28 Incorrect 4 ms 7636 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 3 ms 7380 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 3 ms 7380 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 4 ms 7508 KB Output is correct
7 Correct 5 ms 7524 KB Output is correct
8 Correct 5 ms 7636 KB Output is correct
9 Correct 4 ms 7636 KB Output is correct
10 Correct 85 ms 27968 KB Output is correct
11 Correct 112 ms 32448 KB Output is correct
12 Correct 106 ms 32052 KB Output is correct
13 Correct 110 ms 33512 KB Output is correct
14 Correct 121 ms 36800 KB Output is correct
15 Correct 91 ms 28000 KB Output is correct
16 Correct 177 ms 34496 KB Output is correct
17 Correct 170 ms 33776 KB Output is correct
18 Correct 178 ms 35288 KB Output is correct
19 Correct 241 ms 38484 KB Output is correct
20 Correct 244 ms 41516 KB Output is correct
21 Correct 236 ms 43016 KB Output is correct
22 Correct 251 ms 42188 KB Output is correct
23 Correct 239 ms 42784 KB Output is correct
24 Correct 251 ms 42604 KB Output is correct
25 Correct 242 ms 41224 KB Output is correct
26 Correct 249 ms 42304 KB Output is correct
27 Correct 236 ms 40884 KB Output is correct
28 Correct 4 ms 7636 KB Output is correct
29 Incorrect 4 ms 7636 KB Output isn't correct
30 Halted 0 ms 0 KB -