Submission #863647

#	Time	Username	Problem	Language	Result	Execution time	Memory
863647		3omar_ahmed	Inside information (BOI21_servers)	C++17	0 / 100	46 ms	4816 KiB

servers

#include <bits/stdc++.h>
using namespace std ;
#define int long long
#define endl '\n'
#define all(a) a.begin() , a.end()
#define alr(a) a.rbegin() , a.rend()
const int N = 2e5 + 10;

int n, m, id = 0;
vector < int > flatten, depth, st;
vector < array < int , 3 >> queries;
vector < vector < int >> mx_inc, mx_dec, nxt;
vector < vector < pair < int , int >>> adj, increase, decrease;

void dfs(int node, int par, int last) {
    increase[0][node] = decrease[0][node] = {par, last};
    depth[node] = depth[par] + 1;
    st[node] = flatten.size();
    flatten.push_back(node);
    
    for(auto child : adj[node]) {
        if(child.first == par) continue;
        dfs(child.first, node, child.second);
        flatten.push_back(node);
    }
}

void build() {
    nxt[0] = flatten;
    for(int i = 1 ; (1ll << i) <= flatten.size() ; i++) {
        for(int j = 0 ; j + (1ll << i) <= flatten.size() ; j++) {
            int a = nxt[i - 1][j], b = nxt[i - 1][j + (1ll << (i - 1))];
            if(depth[a] < depth[b]) {
                nxt[i][j] = a;  
            } else {
                nxt[i][j] = b;
            }
        }
    }
}

int LCA(int l, int r) {
    l = st[l], r = st[r];
    if (l > r) swap(l, r);
    int pw = __lg(r - l + 1);
    int a = nxt[pw][l], b = nxt[pw][r - (1 << pw) + 1];
    if(depth[a] < depth[b]) {
        return a;
    } else {
        return b;
    }
}

int dist(int u, int v) {
    return depth[u] + depth[v] - 2 * depth[LCA(u, v)];
}

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);

    cin >> n >> m;
    depth = st = vector < int > (n + 2);
    adj = vector < vector < pair < int , int >>> (n + 1);
    nxt = vector < vector < int >> (22, vector < int > (n * 2 + 5));
    mx_dec = vector < vector < int >> (22, vector < int > (n + 2, 1e9));
    mx_inc = vector < vector < int >> (22, vector < int > (n + 2, -1e9));
    increase = decrease = vector < vector < pair < int , int >>> (22, vector < pair < int , int >> (n + 1));
    
    for(int i = 0 ; i < m + n - 1 ; i++) {
        int a, b; string ty; 
        cin >> ty >> a >> b;
        if(ty == "S") {
            adj[a].push_back({b, i + 1});
            adj[b].push_back({a, i + 1});
        } else if(ty == "Q") {
            queries.push_back({a, b, i + 1});
        }
    }
    
    dfs(1, 0, 0), build();
    
    for(int i = 1 ; i <= n ; i++) {
        mx_dec[0][i] = decrease[0][i].second;
        // cout << "(" << increase[0][i].first << ", " << increase[0][i].second << "), (" << decrease[0][i].first << ", " << decrease[0][i].second << ")" << endl;
    }
    // cout << endl;

    for(int i = 1 ; i <= 20 ; i++) {
        for(int j = 1 ; j <= n ; j++) {

            auto a = increase[i - 1][j];
            if(a.first != -1) {
                auto b = increase[i - 1][a.first];
                if(a.second <= b.second) {
                    increase[i][j] = b;
                } else {
                    increase[i][j] = {-1, -1};
                }
            }

            a = decrease[i - 1][j];
            if(a.first != -1) {
                auto b = decrease[i - 1][a.first];
                if(a.second >= b.second) {
                    decrease[i][j] = b;
                    mx_dec[i][j] = a.second;
                } else {
                    decrease[i][j] = {-1, -1};
                }
            }

            // cerr << "(" << increase[i][j].first << ", " << increase[i][j].second << "), (" << decrease[i][j].first << ", " << decrease[i][j].second << ")" << endl;
        }
    }

    for(auto i : queries) {
        int l = i[0], r = i[1], t = i[2];
        int lc = LCA(l, r);
        int d1 = dist(l, LCA(l, r));
        int d2 = dist(r, LCA(l, r));

        int val1 = 0;
        bool check1 = 1;
        for(int i = 20 ; i >= 0 ; i--) {
            if(d1 & (1ll << i)) {
                if(decrease[i][l].first < 0) {
                    check1 = 0;
                    break;
                } else if(mx_dec[i][l] > t) {
                    check1 = 0;
                    break;
                } else {
                    val1 = decrease[i][l].second;
                    l = decrease[i][l].first;
                }
            }
        }

        int val2 = 0;
        bool check2 = 1;
        for(int i = 20 ; i >= 0 ; i--) {
            if(d2 & (1ll << i)) {
                if(increase[i][r].first < 0) {
                    check2 = 0;
                    break;
                } else if(increase[i][r].second > t) {
                    check1 = 0;
                    break;
                } else {
                    val2 = increase[i][r].second;
                    r = increase[i][r].first;
                }
            }
        }

        cout << (check1 && check2 && val1 >= val2? "yes" : "no") << endl;
    }
    return 0 ;
}

Compilation message (stderr)

servers.cpp: In function 'void build()':
servers.cpp:30:32: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for(int i = 1 ; (1ll << i) <= flatten.size() ; i++) {
      |                     ~~~~~~~~~~~^~~~~~~~~~~~~~~~~
servers.cpp:31:40: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |         for(int j = 0 ; j + (1ll << i) <= flatten.size() ; j++) {
      |                         ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
servers.cpp: In function 'int main()':
servers.cpp:118:13: warning: unused variable 'lc' [-Wunused-variable]
  118 |         int lc = LCA(l, r);
      |             ^~

• Subtask 1: 0 / 2.5
• Subtask 2: 0 / 2.5
• Subtask 3: 0 / 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