oj.uz

Submission #441216

# Submission time Handle Problem Language Result Execution time Memory
441216 2021-07-04T17:08:39 Z Ozy Inside information (BOI21_servers) C++17
5 / 100
 142 ms 44304 KB 
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (int i = (a); i <= (b); i++)
#define repa(i,a,b) for (int i = (a); i >= (b); i--)
#define lli long long
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "

#define MAX 120000
#define des first
#define val second

struct x{
    lli prof;
    lli creciente;
    lli decreciente;
};

lli n,q,a,b,ta,tb,cambio,k,w,c;
lli padres[19][MAX+2],tam[MAX+2],pas[MAX+2];
vector< pair<lli,lli> > hijos[MAX+2];
x nodos[MAX+2];
vector<x> querys;
char tipo;

void une(lli pos, lli padre, lli p) {

    lli nuevo,cont = 1;
    padres[0][pos] = padre;
    nuevo = padre;

    nodos[pos].prof = p;

    while (padres[cont-1][nuevo] != 0) {
        padres[cont][pos] = padres[cont-1][nuevo];
        nuevo = padres[cont][pos];
        cont++;
    }

    for (auto h : hijos[pos]){
        if (h.des == padre) continue;

        if (h.val > pas[pos]) {
            nodos[h.des].creciente = nodos[pos].creciente + 1;
            nodos[h.des].decreciente = 1;
        }
        else {
            nodos[h.des].decreciente = nodos[pos].decreciente + 1;
            nodos[h.des].creciente = 1;
        }

        pas[h.des] = h.val;
        une(h.des,pos,p+1);
    }
}

lli lift(lli pp, lli dis) {

    lli cont = 0;
    while (dis > 0) {
        if (dis&1) pp = padres[cont][pp];
        cont++;
        dis /= 2;
    }
    return pp;
}

lli LCA(lli x, lli y) {

   repa(i,17,0) {
        if (padres[i][x] != padres[i][y]) {
            y = padres[i][y];
            x = padres[i][x];
        }
   }

   y = padres[0][y];
    return y;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> q;

    q += n-1;
    rep(T,1,q) {
        cin >> tipo;
        if (tipo == 'S') {
            cin >> a >> b;
            hijos[a].push_back({b,T});
            hijos[b].push_back({a,T});
        }
        else if (tipo == 'Q') {
            cin >> a >> b;
            querys.push_back({T,a,b});
        }
        else if (tipo == 'C') {
            cin >> a;
            //vacio
        }
    }

    pas[1] = 0;
    une(1,0,1);

    //rep(i,1,n) {
    //    cout << "Nodo " << i << endl;
    //    debugsl(nodos[i].creciente);
    //    debugsl(nodos[i].decreciente);
    //    debugsl(pas[i]);
    //    debug(nodos[i].prof);
    //}

    for (auto act : querys) {

        a = act.creciente;
        b = act.decreciente;
        w = act.prof;
        if (a == b) {cout << "yes\n"; continue;}

        cambio = true;
        if (nodos[a].prof > nodos[b].prof) {swap(a,b); cambio = false;}

        c = lift(b ,nodos[b].prof-nodos[a].prof);
        if (c != a) c = LCA(a,c);

        if (cambio) {

            k = nodos[b].prof - nodos[b].decreciente;
            if (k > nodos[c].prof) {cout << "no\n"; continue;}

            k = nodos[a].prof - nodos[a].creciente;
            if (k > nodos[c].prof) {cout << "no\n"; continue;}

            if (a == c){
                c = lift(b ,nodos[b].prof-nodos[a].prof-1);
                if (pas[c] > w) {cout << "no\n"; continue;}
            }
            else if (pas[a] > w) {cout << "no\n"; continue;}

            cout << "yes\n";

        }
        else {
            k = nodos[a].prof - nodos[a].decreciente;
            if (k > nodos[c].prof) {cout << "no\n"; continue;}

            k = nodos[b].prof - nodos[b].creciente;
            if (k > nodos[c].prof) {cout << "no\n"; continue;}

            if (pas[b] > w) {cout << "no\n"; continue;}

            cout << "yes\n";
        }


    }

}

Subtask #1
0 / 2.5

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

Subtask #2
0 / 2.5

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

Subtask #3
0 / 2.5

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

Subtask #4
0 / 2.5

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

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 7408 KB Output is correct
2 Correct 139 ms 44008 KB Output is correct
3 Correct 139 ms 44016 KB Output is correct
4 Correct 140 ms 43504 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 7408 KB Output is correct
2 Correct 139 ms 44008 KB Output is correct
3 Correct 139 ms 44016 KB Output is correct
4 Correct 140 ms 43504 KB Output is correct
5 Incorrect 32 ms 7100 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 35 ms 7420 KB Output is correct
2 Correct 132 ms 44148 KB Output is correct
3 Correct 129 ms 44304 KB Output is correct
4 Correct 142 ms 43372 KB Output is correct
5 Incorrect 37 ms 7348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 35 ms 7420 KB Output is correct
2 Correct 132 ms 44148 KB Output is correct
3 Correct 129 ms 44304 KB Output is correct
4 Correct 142 ms 43372 KB Output is correct
5 Incorrect 37 ms 7348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

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

Subtask #12
0 / 17.5

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