oj.uz

Submission #571184

# Submission time Handle Problem Language Result Execution time Memory
571184 2022-06-01T12:09:49 Z 2fat2code Swapping Cities (APIO20_swap) C++17
0 / 100
 172 ms 40108 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{
        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]];
    }
}

Compilation message

swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:86:27: warning: 'curr' may be used uninitialized in this function [-Wmaybe-uninitialized]
   86 |             if(lca[curr][i] != 0 && !is_lca(lca[curr][i], Y)) curr = lca[curr][i];
      |                ~~~~~~~~~~~^

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7508 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 5 ms 7380 KB Output is correct
5 Correct 5 ms 7508 KB Output is correct
6 Correct 6 ms 7508 KB Output is correct
7 Correct 6 ms 7636 KB Output is correct
8 Correct 6 ms 7604 KB Output is correct
9 Correct 91 ms 28000 KB Output is correct
10 Correct 109 ms 32540 KB Output is correct
11 Correct 106 ms 32148 KB Output is correct
12 Correct 116 ms 33484 KB Output is correct
13 Correct 112 ms 36672 KB Output is correct
14 Correct 109 ms 27996 KB Output is correct
15 Correct 163 ms 34484 KB Output is correct
16 Correct 172 ms 33768 KB Output is correct
17 Correct 167 ms 35340 KB Output is correct
18 Correct 165 ms 38504 KB Output is correct
19 Incorrect 61 ms 13844 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7508 KB Output is correct
3 Incorrect 151 ms 40108 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

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

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 7276 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7508 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 5 ms 7380 KB Output is correct
5 Correct 5 ms 7508 KB Output is correct
6 Correct 6 ms 7508 KB Output is correct
7 Correct 6 ms 7636 KB Output is correct
8 Correct 6 ms 7604 KB Output is correct
9 Correct 91 ms 28000 KB Output is correct
10 Correct 109 ms 32540 KB Output is correct
11 Correct 106 ms 32148 KB Output is correct
12 Correct 116 ms 33484 KB Output is correct
13 Correct 112 ms 36672 KB Output is correct
14 Correct 109 ms 27996 KB Output is correct
15 Correct 163 ms 34484 KB Output is correct
16 Correct 172 ms 33768 KB Output is correct
17 Correct 167 ms 35340 KB Output is correct
18 Correct 165 ms 38504 KB Output is correct
19 Incorrect 151 ms 40108 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 7276 KB Output isn't correct
2 Halted 0 ms 0 KB -