oj.uz

Submission #935657

# Submission time Handle Problem Language Result Execution time Memory
935657 2024-02-29T10:33:25 Z berr Inside information (BOI21_servers) C++17
50 / 100
 370 ms 125460 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 21 ms 6864 KB Output is correct
2 Correct 35 ms 9776 KB Output is correct
3 Correct 28 ms 9784 KB Output is correct
4 Correct 51 ms 9612 KB Output is correct
5 Correct 42 ms 9660 KB Output is correct
6 Correct 27 ms 9672 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 21 ms 6864 KB Output is correct
2 Correct 35 ms 9776 KB Output is correct
3 Correct 28 ms 9784 KB Output is correct
4 Correct 51 ms 9612 KB Output is correct
5 Correct 42 ms 9660 KB Output is correct
6 Correct 27 ms 9672 KB Output is correct
7 Incorrect 26 ms 6864 KB Extra information in the output file
8 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 20 ms 5572 KB Output is correct
2 Correct 219 ms 119676 KB Output is correct
3 Correct 195 ms 119632 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 20 ms 5572 KB Output is correct
2 Correct 219 ms 119676 KB Output is correct
3 Correct 195 ms 119632 KB Output is correct
4 Incorrect 19 ms 6612 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 5596 KB Output is correct
2 Correct 212 ms 124856 KB Output is correct
3 Correct 229 ms 125116 KB Output is correct
4 Correct 277 ms 124496 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 5596 KB Output is correct
2 Correct 212 ms 124856 KB Output is correct
3 Correct 229 ms 125116 KB Output is correct
4 Correct 277 ms 124496 KB Output is correct
5 Incorrect 21 ms 6464 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 5588 KB Output is correct
2 Correct 202 ms 121408 KB Output is correct
3 Correct 210 ms 121388 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 5588 KB Output is correct
2 Correct 202 ms 121408 KB Output is correct
3 Correct 210 ms 121388 KB Output is correct
4 Incorrect 20 ms 6268 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 21 ms 6408 KB Output is correct
2 Correct 231 ms 125376 KB Output is correct
3 Correct 204 ms 125100 KB Output is correct
4 Correct 284 ms 124272 KB Output is correct
5 Correct 20 ms 6096 KB Output is correct
6 Correct 194 ms 121272 KB Output is correct
7 Correct 220 ms 121384 KB Output is correct
8 Correct 263 ms 122092 KB Output is correct
9 Correct 250 ms 122040 KB Output is correct
10 Correct 338 ms 122752 KB Output is correct
11 Correct 370 ms 122564 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 21 ms 6408 KB Output is correct
2 Correct 231 ms 125376 KB Output is correct
3 Correct 204 ms 125100 KB Output is correct
4 Correct 284 ms 124272 KB Output is correct
5 Correct 20 ms 6096 KB Output is correct
6 Correct 194 ms 121272 KB Output is correct
7 Correct 220 ms 121384 KB Output is correct
8 Correct 263 ms 122092 KB Output is correct
9 Correct 250 ms 122040 KB Output is correct
10 Correct 338 ms 122752 KB Output is correct
11 Correct 370 ms 122564 KB Output is correct
12 Incorrect 21 ms 6612 KB Extra information in the output file
13 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 25 ms 6508 KB Output is correct
2 Correct 36 ms 9652 KB Output is correct
3 Correct 29 ms 9668 KB Output is correct
4 Correct 55 ms 9972 KB Output is correct
5 Correct 43 ms 9788 KB Output is correct
6 Correct 27 ms 9664 KB Output is correct
7 Correct 25 ms 7124 KB Output is correct
8 Correct 206 ms 119544 KB Output is correct
9 Correct 201 ms 119596 KB Output is correct
10 Correct 22 ms 7124 KB Output is correct
11 Correct 210 ms 125460 KB Output is correct
12 Correct 209 ms 124860 KB Output is correct
13 Correct 274 ms 124436 KB Output is correct
14 Correct 21 ms 5576 KB Output is correct
15 Correct 189 ms 121276 KB Output is correct
16 Correct 197 ms 121440 KB Output is correct
17 Correct 281 ms 121964 KB Output is correct
18 Correct 248 ms 121788 KB Output is correct
19 Correct 323 ms 122812 KB Output is correct
20 Correct 356 ms 122436 KB Output is correct
21 Correct 212 ms 120508 KB Output is correct
22 Correct 213 ms 120216 KB Output is correct
23 Correct 226 ms 121016 KB Output is correct
24 Correct 227 ms 121356 KB Output is correct
25 Correct 255 ms 121272 KB Output is correct
26 Correct 221 ms 120716 KB Output is correct
27 Correct 207 ms 120652 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 25 ms 6508 KB Output is correct
2 Correct 36 ms 9652 KB Output is correct
3 Correct 29 ms 9668 KB Output is correct
4 Correct 55 ms 9972 KB Output is correct
5 Correct 43 ms 9788 KB Output is correct
6 Correct 27 ms 9664 KB Output is correct
7 Correct 25 ms 7124 KB Output is correct
8 Correct 206 ms 119544 KB Output is correct
9 Correct 201 ms 119596 KB Output is correct
10 Correct 22 ms 7124 KB Output is correct
11 Correct 210 ms 125460 KB Output is correct
12 Correct 209 ms 124860 KB Output is correct
13 Correct 274 ms 124436 KB Output is correct
14 Correct 21 ms 5576 KB Output is correct
15 Correct 189 ms 121276 KB Output is correct
16 Correct 197 ms 121440 KB Output is correct
17 Correct 281 ms 121964 KB Output is correct
18 Correct 248 ms 121788 KB Output is correct
19 Correct 323 ms 122812 KB Output is correct
20 Correct 356 ms 122436 KB Output is correct
21 Correct 212 ms 120508 KB Output is correct
22 Correct 213 ms 120216 KB Output is correct
23 Correct 226 ms 121016 KB Output is correct
24 Correct 227 ms 121356 KB Output is correct
25 Correct 255 ms 121272 KB Output is correct
26 Correct 221 ms 120716 KB Output is correct
27 Correct 207 ms 120652 KB Output is correct
28 Incorrect 22 ms 7128 KB Extra information in the output file
29 Halted 0 ms 0 KB -