제출 #399124

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
399124		egekabas	Inside information (BOI21_servers)	C++14	2.50 / 100	205 ms	57788 KiB

servers

#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<int, int> pii;
typedef pair<ld, ld> pld;
int n, k;

char t[240009];
int x[240009];
int y[240009];

vector<pii> g[120009];

int dad[120009][25];
int depth[120009];

int pval[120009][25];
int incr[120009][25];
int decr[120009][25];

void dfs(int v, int prt){
    dad[v][0] = prt;
    depth[v] = depth[prt]+1;

    for(int i = 1; i < 25; ++i){
        dad[v][i] = dad[dad[v][i-1]][i-1];
        pval[v][i] = pval[dad[v][i-1]][i-1];
        if(incr[v][i-1] && incr[dad[v][i-1]][i-1] && pval[v][i-1] < pval[dad[v][i-1]][0])
            incr[v][i] = 1;
        if(decr[v][i-1] && decr[dad[v][i-1]][i-1] && pval[v][i-1] > pval[dad[v][i-1]][0])
            decr[v][i] = 1;
    }
    for(auto u : g[v])
        if(u.ff != prt){
            incr[u.ff][0] = decr[u.ff][0] = 1;
            pval[u.ff][0] = u.ss;
            dfs(u.ff, v);
        }
}
int lca(int x, int y){
    if(depth[y] > depth[x])
        swap(x, y);
    for(int i = 24; i >= 0; --i)
        if(depth[dad[x][i]] >= depth[y])
            x = dad[x][i];
    if(x == y) return x;
    for(int i = 24; i >= 0; --i)
        if(dad[x][i] != dad[y][i]){
            x = dad[x][i];
            y = dad[y][i];
        }
    return dad[x][0];
}
struct retst{
    int incr = 1, decr = 1, maxi = -1, last = -1;
};
retst goup(int x, int y){
    retst ret;
    for(int i = 24; i >= 0; --i)
        if(depth[dad[x][i]] >= depth[y]){
            if(ret.last != -1 && ret.last > pval[x][0])
                ret.incr = 0;
            if(ret.last != -1 && ret.last < pval[x][0])
                ret.decr = 0;
            ret.maxi = max({ret.maxi, pval[x][0], pval[x][i]});
            ret.last = pval[x][i];
            x = dad[x][i];
        }
    return ret;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);

    cin >> n >> k;
    for(int i = 0; i < n+k-1; ++i){
        cin >> t[i];
        if(t[i] == 'C')
            cin >> x[i];
        else
            cin >> x[i] >> y[i];
        if(t[i] == 'S'){
            g[x[i]].pb({y[i], i});
            g[y[i]].pb({x[i], i});
        }
    }
    dfs(1, 0);
    for(int i = 0; i < n+k-1; ++i){
        if(t[i] == 'S') continue;
        else if(t[i] == 'Q'){
            int lc = lca(x[i], y[i]);
            retst a = goup(x[i], lc);
            retst b = goup(y[i], lc);
            if(a.decr && b.incr && (a.last == -1 || b.last == -1 || a.last > b.last) && max(a.maxi, b.maxi) <= i)
                cout << "yes\n";
            else
                cout << "no\n";
        }
        else{
            cout << "0\n";
            assert(0);
        }
    }
}

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