oj.uz

Submission #612672

# Submission time Handle Problem Language Result Execution time Memory
612672 2022-07-29T20:09:00 Z AugustinasJucas Swapping Cities (APIO20_swap) C++14
6 / 100
 420 ms 45628 KB 
#include "swap.h"
#include <bits/stdc++.h>
using namespace std;

vector<pair<int, pair<int, int> > > brn;
const int dydis = 1e5 + 10;
int tevas[dydis];
int kadaNelinija[dydis];
bool neraLinija[dydis] = {};
vector<int> nodes[dydis];
int A[dydis], B[dydis];
int n, m;
vector<pair<int, int> > gr[dydis];
void add(int a, int b, int w) {
    //cout << "brn " << a << " -- " << b << ", w = " << w << endl;
    gr[a].push_back({b, w});
    gr[b].push_back({a, w});
}
int fp(int v) {
    if(tevas[v] == v) return v;
    return tevas[v] = fp(tevas[v]);
}
void conn(int a, int b, int t) {
    int inA = a; int inB = b;

    a = fp(a);
    b = fp(b);
 //   //cout << "jungiu " << inA << "(yra_linija = " << !neraLinija[a] <<") su " << inB  << "(yra_linija = " << !neraLinija[b] << ")" << endl;
    if(a == b) {
        if(neraLinija[a]) return ;
        neraLinija[a] = true;
        for(auto x : nodes[a]) kadaNelinija[x] = t;
    }else {
        add(inA, inB, t);
        if(neraLinija[a] || neraLinija[b]) {
            if(!neraLinija[a]) for(auto x : nodes[a]) kadaNelinija[x] = t;
            if(!neraLinija[b]) for(auto x : nodes[b]) kadaNelinija[x] = t;
        }
        if(nodes[a].size() > nodes[b].size()) swap(a, b);
        // a ---> b

        if(!neraLinija[a] && !neraLinija[b]) {
            set<int> galai = {A[a], B[a], A[b], B[b]};
            ////cout << "linju galai: "; for(auto x : galai) //cout << x << " ";
          //  //cout << ", o as jungiu " << inA << " su " << inB << endl;
            if(galai.count(inA) && galai.count(inB)) {
                /// sujungiau liniju galus
                int na, nb;
                if(A[a] == inA || A[a] == inB) {
                    na = B[a];
                }else {
                    na = A[a];
                }
                if(A[b] == inA || A[b] == inB) {
                    nb = B[b];
                }else {
                    nb = A[b];
                }
                A[b] = na;
                B[b] = nb;
            }else {
             //   for(auto x : nodes[a]) kadaNelinija[x] = t;
               // for(auto x : nodes[b]) kadaNelinija[x] = t;
                neraLinija[b] = true;
            }
        }

        tevas[a] = b;
        for(auto x : nodes[a]) nodes[b].push_back(x);

    }
}
int dbInd = 0;
int enter[dydis], leave[dydis];
int rotW[dydis], par[dydis];
int h[dydis];
void dfs(int v, int came) {
    enter[v] = dbInd++;
    par[v] = came;
   // //cout << "esi " << v << endl;
    for(auto x : gr[v]) {
        if(x.first == came) continue;
        h[x.first] = h[v] + 1;
        rotW[x.first] = x.second;
        //cout << "rot[" << x.first << "] = " << x.second <<  ", T./Y., " << rotW[x.first] << endl;

        dfs(x.first, v);
    }
    leave[v] = dbInd++;
}
const int dd = 20;
int lft[dydis][dd];
int mx[dydis][dd];
void calc() {
    for(int i = 0; i < n; i++) {
        lft[i][0] = par[i];
        //cout << "rotw[" << i << "] = " << rotW[i] << endl;
        mx[i][0] = rotW[i];
        //cout << "mx[" << i << "][" << 0 << "] = " << mx[i][0] << endl;
    }
    for(int j = 1; j < dd; j++) {
        for(int i = 0; i < n; i++) {
            lft[i][j] = lft[lft[i][j-1]][j-1];
        }
    }
    for(int j = 1; j < dd; j++) {
        for(int i = 0; i < n; i++) {
            mx[i][j] = max(mx[i][j-1], mx[ lft[i][j-1] ][j-1]);
            //cout << "mx[" << i << "][" << j << "] = " << mx[i][j] << endl;
        }
    }

}
bool isAnc(int a, int b) {
    return (enter[a] <= enter[b] && leave[b] <= leave[a]);
}

int lca(int a, int b) {
    if(isAnc(a, b)) return a;
    if(isAnc(b, a)) return b;
    for(int i = dd-1; i > -1; i--) {
        if(!isAnc(lft[a][i], b)) {
            a = lft[a][i];
        }
    }
    return par[a];
}

int mxPerBrn(int a, int kek) {
    int ret = 0;
    for(int i = dd-1; i > -1; i--) {
        if((1 << i) <= kek) {
            ret = max(ret, mx[a][i]);
            a = lft[a][i];
            kek -= (1 << i);
        }
    }
    return ret;
}
int mxInPath(int a, int b) {
    int v = lca(a, b);
    int kair = mxPerBrn(a, h[a] - h[v]);
    int desn = mxPerBrn(b, h[b] - h[v]);
    return max(kair, desn);
}

void init(int N, int M,
          std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    n = N; m = M;
    for(int i = 0; i < n; i++)  {
        tevas[i] = i;
        nodes[i] = {i};
        A[i] = i; B[i] = i;
        neraLinija[i] = false;
        kadaNelinija[i] = -1;
    }

    for(int i = 0; i < m; i++) {
        brn.push_back({W[i], {U[i], V[i]}});
    }
    sort(brn.begin(), brn.end()); /// nuo maz iki did.

    for(auto x : brn) {
        int a = x.second.first;
        int b = x.second.second;
        int w = x.first;
        conn(a, b, w);
    }
    h[0] = 0;
    dfs(0, 0);
    calc();

    for(int i = 0; i < n; i++) {
        //cout << "virsune nr " << i << " tampa nebe linija, kai w = " << kadaNelinija[i] << endl;
    }

   /* for(int i = 0; i < n; i++) {
        for(int j = i+1; j < n; j++) {
            int res = mxInPath(i, j);
            //cout << "min max val tarp " << i << " ir " << j << " yra " << res << endl;
        }
        //cout << endl;
    }*/


}

int getMinimumFuelCapacity(int X, int Y) {
    if(kadaNelinija[fp(X)] == -1 || kadaNelinija[fp(Y)] == -1) return -1;
    int ret = mxInPath(X, Y);
    ret = max(ret, max(kadaNelinija[fp(X)], kadaNelinija[fp(Y)]));
    return ret;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 5076 KB Output is correct
5 Correct 4 ms 5332 KB Output is correct
6 Correct 3 ms 5352 KB Output is correct
7 Correct 3 ms 5332 KB Output is correct
8 Correct 4 ms 5360 KB Output is correct
9 Correct 138 ms 33980 KB Output is correct
10 Correct 176 ms 40944 KB Output is correct
11 Correct 178 ms 40068 KB Output is correct
12 Correct 185 ms 42280 KB Output is correct
13 Correct 148 ms 41028 KB Output is correct
14 Correct 136 ms 33320 KB Output is correct
15 Correct 230 ms 43188 KB Output is correct
16 Correct 227 ms 40628 KB Output is correct
17 Correct 262 ms 45628 KB Output is correct
18 Correct 207 ms 41616 KB Output is correct
19 Correct 100 ms 14508 KB Output is correct
20 Correct 375 ms 43648 KB Output is correct
21 Correct 396 ms 41780 KB Output is correct
22 Correct 420 ms 45228 KB Output is correct
23 Correct 351 ms 42696 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Incorrect 167 ms 35356 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 5076 KB Output is correct
5 Correct 4 ms 5332 KB Output is correct
6 Correct 3 ms 5352 KB Output is correct
7 Correct 3 ms 5332 KB Output is correct
8 Correct 4 ms 5360 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Incorrect 4 ms 5332 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 4 ms 5332 KB Output is correct
7 Correct 3 ms 5352 KB Output is correct
8 Correct 3 ms 5332 KB Output is correct
9 Correct 4 ms 5360 KB Output is correct
10 Correct 138 ms 33980 KB Output is correct
11 Correct 176 ms 40944 KB Output is correct
12 Correct 178 ms 40068 KB Output is correct
13 Correct 185 ms 42280 KB Output is correct
14 Correct 148 ms 41028 KB Output is correct
15 Incorrect 4 ms 5332 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 5076 KB Output is correct
5 Correct 4 ms 5332 KB Output is correct
6 Correct 3 ms 5352 KB Output is correct
7 Correct 3 ms 5332 KB Output is correct
8 Correct 4 ms 5360 KB Output is correct
9 Correct 138 ms 33980 KB Output is correct
10 Correct 176 ms 40944 KB Output is correct
11 Correct 178 ms 40068 KB Output is correct
12 Correct 185 ms 42280 KB Output is correct
13 Correct 148 ms 41028 KB Output is correct
14 Correct 136 ms 33320 KB Output is correct
15 Correct 230 ms 43188 KB Output is correct
16 Correct 227 ms 40628 KB Output is correct
17 Correct 262 ms 45628 KB Output is correct
18 Correct 207 ms 41616 KB Output is correct
19 Incorrect 167 ms 35356 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 4 ms 5332 KB Output is correct
7 Correct 3 ms 5352 KB Output is correct
8 Correct 3 ms 5332 KB Output is correct
9 Correct 4 ms 5360 KB Output is correct
10 Correct 138 ms 33980 KB Output is correct
11 Correct 176 ms 40944 KB Output is correct
12 Correct 178 ms 40068 KB Output is correct
13 Correct 185 ms 42280 KB Output is correct
14 Correct 148 ms 41028 KB Output is correct
15 Correct 136 ms 33320 KB Output is correct
16 Correct 230 ms 43188 KB Output is correct
17 Correct 227 ms 40628 KB Output is correct
18 Correct 262 ms 45628 KB Output is correct
19 Correct 207 ms 41616 KB Output is correct
20 Incorrect 167 ms 35356 KB Output isn't correct
21 Halted 0 ms 0 KB -