Submission #900534

#	Time	Username	Problem	Language	Result	Execution time	Memory
900534		Shayan86	Inside information (BOI21_servers)	C++14	2.50 / 100	106 ms	38288 KiB

servers

#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// Ofast, O0, O1, O2, O3, unroll-loops, fast-math, trapv

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;

#define Mp          make_pair
#define sep         ' '
#define endl        '\n'
#define F	        first
#define S	        second
#define pb          push_back
#define all(x)      (x).begin(),(x).end()
#define kill(res)	cout << res << '\n', exit(0);
#define set_dec(x)	cout << fixed << setprecision(x);
#define fast_io     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io     freopen("input.txt", "r", stdin) ; freopen("output.txt", "w", stdout);

const ll L = 20;
const ll N = 12e4 + 50;
const ll Mod = 1e9 + 7;

ll n, k, par[N][L], a[N], b[N], val[N], h[N], sa[N], sb[N];

vector<pii> adj[N];
vector<pair<char, pii>> qu;

void dfs(int v, int p = 0){
    par[v][0] = p;
    for(int i = 1; i < L; i++){
        if(!par[v][i-1]) break;
        par[v][i] = par[par[v][i-1]][i-1];
    }
    for(auto [u, w]: adj[v]){
        if(u == p) continue;
        h[u] = h[v] + 1; dfs(u, v); val[u] = w;
    }

    if(p && par[v][1]){
        a[v] = (val[v] > val[p]); b[v] = 1 - a[v];
    }
}

void cal(int v, int p = 0){
    for(auto [u, w]: adj[v]){
        if(u == p) continue;
        sa[u] = sa[v] + a[u];
        sb[u] = sb[v] + b[u];
        cal(u, v);
    }
}

int getPar(int v, int k){
    for(int i = 0; i < L; i++){
        if(k >> i & 1) v = par[v][i];
    }
    return v;
}

int lca(int u, int v){
    if(h[v] < h[u]) swap(u, v);
    v = getPar(v, h[v] - h[u]);
    if(u == v) return v;

    for(int i = L-1; i >= 0; i--){
        if(par[v][i] != par[u][i]){
            v = par[v][i]; u = par[u][i];
        }
    }
    return par[v][0];
}

int main(){
    fast_io;

    cin >> n >> k;

    int ci = 0;
    for(int i = 1; i < n+k; i++){
        char t; int u, v;
        cin >> t >> u >> v;
        qu.pb({t, {u, v}});
        if(t == 'S'){
            ci++;
            adj[u].pb({v, ci});
            adj[v].pb({u, ci});
        }
    }

    dfs(1); cal(1);

    ci = 0;
    for(int i = 0; i < n+k-1; i++){
        char t; int u, v; // v -> u
        t = qu[i].F; u = qu[i].S.F; v = qu[i].S.S;
        if(t == 'S'){
            ci++; continue;
        }

        if(u == v){
            cout << "yes\n"; continue;
        }

        int ulv = lca(u, v);
        int up = getPar(u, h[u] - h[ulv] - 1);
        int vp = getPar(v, h[v] - h[ulv] - 1);

        if(ulv == u){
            bool ch = (sb[v] - sb[vp] == h[v] - h[vp]);
            ch &= (val[vp] <= ci);
            cout << (ch ? "yes" : "no") << endl;
            continue;
        }
        if(ulv == v){
            bool ch = (sa[u] - sa[up] == h[u] - h[up]);
            ch &= (val[u] <= ci);
            cout << (ch ? "yes" : "no") << endl;
            continue;
        }

        bool ch = (val[vp] < val[up]);
        if(u != up) ch &= (sa[u] - sa[up] == h[u] - h[up]);
        if(v != vp) ch &= (sb[v] - sb[vp] == h[v] - h[vp]);
        ch &= (val[u] <= ci);
        cout << (ch ? "yes" : "no") << endl;
    }

}

Compilation message (stderr)

servers.cpp: In function 'void dfs(int, int)':
servers.cpp:39:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   39 |     for(auto [u, w]: adj[v]){
      |              ^
servers.cpp: In function 'void cal(int, int)':
servers.cpp:50:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   50 |     for(auto [u, w]: adj[v]){
      |              ^

• 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