Submission #935016

#	Time	Username	Problem	Language	Result	Execution time	Memory
935016		berr	Inside information (BOI21_servers)	C++17	0 / 100	24 ms	6864 KiB

servers

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

#define int long long

struct val{
    int n, cnt = 0;
    vector<vector<array<int, 2>>> g;
    vector<array<int, 17>> vu, vd, p;
    vector<array<int, 17>> ma, mi;

    vector<int> ti, to;

    vector<int> d;

    val(){};

    val(vector<vector<array<int, 2>>> _g){
        n = _g.size();
        g = _g;
        d.resize(n, -1); vu.resize(n); 
        vd.resize(n); p.resize(n);
        ti.resize(n); to.resize(n);
        ma.resize(n); mi.resize(n);

        dfs(0, 0);
        for(int i=1; i<17; i++){
            for(int l=0; l<n; l++){
                p[l][i] = p[p[l][i-1]][i-1];
            }
        }

        for(int i=1; i<17; i++){
            for(int l=0; l<n; l++){
                ma[l][i]=max(ma[l][i-1], ma[p[l][i-1]][i-1]);
                mi[l][i]=min(mi[l][i-1], mi[p[l][i-1]][i-1]);

                if(vu[p[l][i-1]][i-1]<=vu[l][i-1]) vu[l][i] = vu[l][i-1];
                else vu[l][i] = 1e18;
                
                if(vd[p[l][i-1]][i-1] >= vd[l][i-1]) vd[l][i] =vd[l][i-1];
                else vd[l][i] = 1e18;
            }
        }

    }

    void dfs(int v, int par){
        d[v] = d[par] +1;
        p[v][0]=par; ti[v] = cnt++;
        for(auto [i, j]: g[v]){
            if(i == par) continue;
            vu[i][0] = j; vd[i][0]=j;
            ma[i][0]=j; mi[i][0]=j;
            dfs(i, v);
        }
        to[v] = cnt++;
    }   

    auto ia(int a, int b){
        return ti[a]<=ti[b] && to[a]>= to[b];
    }

    int operator()(int x, int y){
        if(x==y)return 0;
        // 1e18 if no way
        // max value of that path
        if(ia(x, y)){
            int m = 0, lasty;
            for(int j=16; j>=0; j--){
                if((1<<j) <= d[y] && !ia(y, x)){
                    if(vd[y][j]==1e18) m = 1e18;
                    lasty = ma[x][j];
                    y = p[y][j];
                    if(lasty>vu[y][0]) m = 1e18;
                }
            }
            if(m!=0) return 1e18;
            else return vu[y][0];
        }

        int m = vu[x][0];
        int tmp =m;
        int lastx = m, lasty=vu[y][0];

        for(int j=16; j>=0; j--){
            if((1<<j) <= d[x] && !ia(p[x][j], y)){
                m = max(m, vu[x][j]);
                lastx = mi[x][j];
                x = p[x][j];
                if(lastx<vu[x][0]) m = 1e18;

            }

            if((1<<j) <= d[y] && !ia(p[y][j], x)){
                m = max(m, vd[y][j]);
                lasty = ma[y][j];
                y = p[y][j];
                if(lasty>vu[y][0]) m = 1e18;
            }
        }
        if(m != tmp) return 1e18;
     
        if(!ia(x, y)&&(!ia(y, x))){
            if(vu[x][0]<vu[y][0]) return 1e18;
        }     

        return m;
    }

};

val a;
/*
struct centroid{

};*/
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, k; cin >> n >> k;
    vector<vector<array<int, 2>>> g(n);
    /// a dan b ye erişirkenki max değer
    /// a dan b ye erişim var mı
    int time = 0;
    vector<array<int, 4>> qu;

    for(int i=1; i<n+k; i++){
        char t; cin >> t;
        if (t=='S'){
            time++;
            int a, b; cin >> a >> b;
            a--; b--;
            g[a].push_back({b, time});
            g[b].push_back({a, time});
        }
        else if(t=='Q'){
            int a, b; cin >> a >> b;
            a--; b--;
          //  can i go from b to a 
            qu.push_back({0, a, b, time});
        }
        else{
            int a; cin >> a; a--;
            qu.push_back({1, a, a, time});
        }
    }  

    a = val(g);
    for(auto [i, j, k, l]: qu){

        if(i==0){
            cout<<(a(j, k)<=l?"Yes":"No")<<"\n";
        }
    }

   // centroid c(g);

}

• 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