oj.uz

답안 #445385

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
445385 2021-07-17T20:27:45 Z Ozy Inside information (BOI21_servers) C++17
0 / 100
 40 ms 20712 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 240000
#define costo first
#define des second

struct x {
    lli tipo;
    lli des;
    lli tiempo;
    lli id;
};

lli n,qq,a,b,cent,cont,t;
lli visitados[MAX+2],tam[MAX+2],llego[MAX+2],bit[MAX+2];
char c;
queue<lli> cola;
vector<pair<lli,lli> > hijos[MAX+2];
vector<x> querys[MAX+2];
pair<lli,lli> res[MAX+2];

void actualiza(lli pos,lli val) {
    while (pos <= t) {
        bit[pos] += val;
        pos += pos&(-pos);
    }
}

lli sum(lli pos) {
    lli r = 0;
    while (pos > 0) {
        r += bit[pos];
        pos -= pos&(-pos);
    }
    return r;
}

lli buscaCen (lli pos, lli padre, lli mitad) {
    for (auto h : hijos[pos]){
        if (h.des == padre || visitados[h.des] == 1) continue;
        if (tam[h.des] > mitad) return buscaCen(h.des, pos, mitad);
    }
    return pos;
}

void DFS(lli pos, lli padre) {

    tam[pos] = 1;
    for (auto h : hijos[pos]) {
        if (h.des == padre || visitados[h.des] == 1) continue;
        DFS(h.des, pos);
        tam[pos] += tam[h.des];
    }

}

void ami(lli pos, lli padre, lli ant, vector<lli> &nuevos) {

    nuevos.push_back(pos);
    for (auto h : hijos[pos]) {
        if (h.des == padre || visitados[h.des] == 1) continue;
        if (h.costo > ant) continue;
        ami(h.des,pos,h.costo,nuevos);
    }

}

void aellos(lli pos, lli padre, lli ant, vector<pair<lli,lli> > & acc) {
    acc.push_back({pos,ant});
    for (auto h : hijos[pos]) {
        if (h.des == padre || visitados[h.des] == 1) continue;
        if (h.costo < ant) continue;
        aellos(h.des,pos,h.costo,acc);
    }
}

void solve() {
    lli act;

    while (!cola.empty()) {
        act = cola.front();
        cola.pop();

        DFS(act,0);
        cent = buscaCen(act,0,tam[act]/2);

        sort(hijos[cent].begin(), hijos[cent].end());
        reverse(hijos[cent].begin(),hijos[cent].end());

        vector < pair<lli,lli> > deshacer;
        for (auto h : hijos[cent]) {
            if (visitados[h.des] == 1) continue;

            vector<lli> nuevos;
            ami(h.des,cent,h.costo,nuevos);

            for (auto nodo : nuevos) {

                for (auto q : querys[nodo]) {
                    if (q.tipo == 1) {

                        if (q.des == cent && q.tiempo < h.costo) res[q.id].second = 1;
                        else if (llego[q.des] > 0 && llego[q.des] < q.tiempo) res[q.id].second = 1;

                    }
                    else {

                        res[q.id].second += sum(q.tiempo);
                        if (h.costo < q.tiempo) res[q.id].second++;

                    }
                }
            }

            vector< pair<lli,lli> > accesibles;
            aellos(h.des,cent,h.costo,accesibles);

            for ( auto nodo : accesibles) {
                deshacer.push_back(nodo);
                llego[nodo.first] = nodo.second;
                actualiza(nodo.second,1);
            }
        }

        for (auto q : querys[cent]) {
            if (q.tipo == 1) {
                if (llego[q.des] > 0 && llego[q.des] < q.tiempo) res[q.id].second = 1;
            }
            else {
                res[q.id].second += sum(q.tiempo);
            }
        }

        for (auto borr : deshacer) {
            llego[borr.first] = 0;
            actualiza(borr.second,-1);
        }

        visitados[cent] = 1;
        for (auto h : hijos[cent]) {
            if (visitados[h.des] == 1) continue;
            cola.push(h.des);
        }

    }
}

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

    cin >> n >> qq;
    t = n+qq-1;

    cont = 1;
    rep(i,1,t){
        cin >> c;
        if (c == 'S') {
            cin >> a >> b;
            hijos[a].push_back({i,b});
            hijos[b].push_back({i,a});
        }
        else if (c == 'Q') {
            cin >> a >> b;
            querys[b].push_back({1,a,i,cont});
            res[cont].first = 1;
            cont++;
        }
        else {
            cin >> a;
            querys[a].push_back({2,0,i,cont});
            res[cont].first = 2;
            cont++;
        }
    }

    cola.push(1);
    solve();

    cont--;
    rep(i,1,cont) {
        if (res[i].first == 2) cout << res[i].second+1 << "\n";
        else {
            if (res[i].second == 1) cout << "yes\n";
            else cout << "no\n";
        }
    }
}

Subtask #1
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 39 ms 20712 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 39 ms 20712 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 40 ms 20664 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 40 ms 20664 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 38 ms 20688 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 38 ms 20688 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 38 ms 20672 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 38 ms 20672 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 38 ms 20672 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 38 ms 20672 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 39 ms 20648 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 39 ms 20648 KB Output isn't correct
2 Halted 0 ms 0 KB -