Submission #441229

#	Time	Username	Problem	Language	Result	Execution time	Memory
441229		Ozy	Inside information (BOI21_servers)	C++17	50 / 100	400 ms	44032 KiB

servers

#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];
        }
   }

    ta = x;
    tb = y;
    return padres[0][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;}
                if (pas[tb] > pas[ta]) {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;}
            if (c != a && pas[ta] > pas[tb]) {cout << "no\n"; continue;}

            cout << "yes\n";
        }


    }

}

• Subtask 1: 2.5 / 2.5
• Subtask 2: 0 / 2.5
• Subtask 3: 2.5 / 2.5
• Subtask 4: 0 / 2.5
• Subtask 5: 5 / 5
• Subtask 6: 0 / 5
• Subtask 7: 10 / 10
• Subtask 8: 0 / 10
• Subtask 9: 12.5 / 12.5
• Subtask 10: 0 / 12.5
• Subtask 11: 17.5 / 17.5
• Subtask 12: 0 / 17.5