Submission #935657

#	Time	Username	Problem	Language	Result	Execution time	Memory
935657		berr	Inside information (BOI21_servers)	C++17	50 / 100	370 ms	125460 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, 18>> vu, vd, p;
    vector<array<int, 18>> 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<18; i++){
            for(int l=0; l<n; l++){
                p[l][i] = p[p[l][i-1]][i-1];
            }
        }
 
        for(int i=1; i<18; 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(mi[l][i-1]>=ma[p[l][i-1]][i-1]&&vu[p[l][i-1]][i-1]!=1e18) vu[l][i] = vu[l][i-1];
                else vu[l][i] = 1e18;
                
                if(ma[l][i-1]<=mi[p[l][i-1]][i-1]&&vd[p[l][i-1]][i-1]!=1e18) 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;
            int tmpy=y;
 
            for(int j=17; j>=0; j--){
                if((1<<j) <= d[y] && d[y]-(1<<j)>=d[x]){
                    if(vd[y][j]==1e18) m = 1e18;
                    lasty = ma[y][j];
                    m = max(m, ma[y][j]);
 
                    y = p[y][j];
                    if(lasty>vu[y][0]&&y!=x) m = 1e18;
                }
            }
            if(m==1e18) return 1e18;
            else return m;
 
        }
 
        int m = vu[x][0];
        int tmp =m;
        int lastx = m, lasty=vu[y][0];
 
        for(int j=17; 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 = 1;
    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){
            if(a(j, k)<=l) cout<<"yes\n";
            else cout<<"no\n";
        }
    }
 
   // centroid c(g);
 
}

Compilation message (stderr)

servers.cpp: In member function 'long long int val::operator()(long long int, long long int)':
servers.cpp:71:17: warning: unused variable 'tmpy' [-Wunused-variable]
   71 |             int tmpy=y;
      |                 ^~~~

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