oj.uz

Submission #947867

# Submission time Handle Problem Language Result Execution time Memory
947867 2024-03-17T07:39:36 Z willychan Inside information (BOI21_servers) C++17
50 / 100
 187 ms 46084 KB 
    #include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    //#include<bits/extc++.h>
    //__gnu_pbds
     
     
    struct qT {
        int type;
        int a;
        int d;
        int t;
        qT(int _type,int _a,int _d,int _t):type(_type),a(_a),d(_d),t(_t) {}
    };
    const int N = 120005;
    vector<pair<int,int> > side[N];
    static const int B = 20;
    int P[N][B];
    int iv[N][B];
    int dv[N][B];
    pair<int,int> dfn[N];
     
    struct Qstruct {
        int n;
        int T;
        void dfs(int cur,int p,int v) {
            dfn[cur].first=++T;
            P[cur][0]=p;
            iv[cur][0]=v;
            dv[cur][0]=v;
            for(auto e : side[cur]) {
                if(e.first!=p) dfs(e.first,cur,e.second);
            }
            dfn[cur].second=++T;
        }
        void init(int _n) {
            n = _n;
            T = 0;
			dfs(1,1,0);
			for(int i=0;i<B;i++){
				P[1][i]=1;
				iv[1][i]=-1;
				dv[1][i]=-1;
			}
			for(int j=1;j<B;j++){
				for(int i=2;i<=n;i++){
					P[i][j] = P[P[i][j-1]][j-1];
					if(iv[i][j-1]==-1 || iv[P[i][j-1]][0]<iv[i][j-1]) iv[i][j]=-1;
					else iv[i][j]=iv[P[i][j-1]][j-1];
					if(dv[i][j-1]==-1 || dv[P[i][j-1]][0]>dv[i][j-1]) dv[i][j]=-1;
					else dv[i][j]=dv[P[i][j-1]][j-1];
				}
			}
        }
        bool isanc(int a,int b) {
            return (dfn[a].first<=dfn[b].first)&(dfn[a].second>=dfn[b].second);
        }
        int lca(int a,int b) {
            if(isanc(a,b)) return a;
            if(isanc(b,a)) return b;
            for(int j=B-1; j>=0; j--) {
                if(!isanc(P[a][j],b)) a = P[a][j];
            }
            return P[a][0];
        }
		int dec(int a,int b){
			assert(isanc(a,b));
			assert(a!=b);
			int v = 1e9;
			for(int j=B-1;j>=0;j--){
				if(!isanc(P[b][j],a)){
					if(v==-1 || dv[b][0]>v) v=-1;
					else v=dv[b][j];
					b = P[b][j];
				}
			}
			if(v==-1 || dv[b][0]>v) return -1;
			else return dv[b][0];
		}
		int inc(int a,int b){
			assert(isanc(a,b));
			assert(a!=b);
			int v = -1e9;
			for(int j=B-1;j>=0;j--){
				if(!isanc(P[b][j],a)){
					if(v==-1 || iv[b][0]<v) v=-1;
					else v=iv[b][j];
					b = P[b][j];
				}
			}
			if(v==-1 || iv[b][0]<v) return -1;
			else return iv[b][0];
		}
		bool query(int a,int d,int t){
			if(a==d) return 1;
			if(isanc(a,d)){
				int c = inc(a,d);
				return (c<=t)&&(c!=-1);
			}
			if(isanc(d,a)){
				int c = dec(d,a);
				return (dv[a][0]<=t)&&(c!=-1);
			}
			int c = lca(d,a);
			int na = dec(c,a);
			int nd = inc(c,d);
			if(na==-1 || nd==-1) return 0;
			if(na<nd) return 0;
			return (dv[a][0]<=t);
		}
    };
     
     
     
    int main() {
        ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int n,k;
        cin>>n>>k;
        vector<qT> query;
        for(int i=1; i<=n+k-1; i++) {
            char t;
            cin>>t;
            if(t=='S') {
                int a,b;
                cin>>a>>b;
                side[a].push_back({b,i});
                side[b].push_back({a,i});
            }
            if(t=='Q') {
                int a,d;
                cin>>a>>d;
                query.emplace_back(0,a,d,i);
            }
            if(t=='C') {
                int d;
                cin>>d;
                query.emplace_back(1,0,d,i);
            }
        }
        Qstruct Qans;
        Qans.init(n);
        for(auto cur : query)	{
            if(cur.type==0) {
                if(Qans.query(cur.a,cur.d,cur.t)){
    				cout<<"yes\n";
    			}else{
    				cout<<"no\n";
    			}
            } else {
                cout<<0<<"\n";
            }
        }
        return 0;
    }

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 26 ms 6356 KB Output is correct
2 Correct 37 ms 7960 KB Output is correct
3 Correct 30 ms 8140 KB Output is correct
4 Correct 55 ms 7984 KB Output is correct
5 Correct 35 ms 8136 KB Output is correct
6 Correct 31 ms 7956 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 26 ms 6356 KB Output is correct
2 Correct 37 ms 7960 KB Output is correct
3 Correct 30 ms 8140 KB Output is correct
4 Correct 55 ms 7984 KB Output is correct
5 Correct 35 ms 8136 KB Output is correct
6 Correct 31 ms 7956 KB Output is correct
7 Incorrect 25 ms 6356 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 23 ms 6476 KB Output is correct
2 Correct 137 ms 42064 KB Output is correct
3 Correct 121 ms 42156 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 23 ms 6476 KB Output is correct
2 Correct 137 ms 42064 KB Output is correct
3 Correct 121 ms 42156 KB Output is correct
4 Incorrect 24 ms 6444 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 20 ms 6348 KB Output is correct
2 Correct 124 ms 45612 KB Output is correct
3 Correct 128 ms 45568 KB Output is correct
4 Correct 122 ms 45640 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 6348 KB Output is correct
2 Correct 124 ms 45612 KB Output is correct
3 Correct 128 ms 45568 KB Output is correct
4 Correct 122 ms 45640 KB Output is correct
5 Incorrect 20 ms 6352 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 25 ms 6472 KB Output is correct
2 Correct 127 ms 42428 KB Output is correct
3 Correct 115 ms 43096 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 6472 KB Output is correct
2 Correct 127 ms 42428 KB Output is correct
3 Correct 115 ms 43096 KB Output is correct
4 Incorrect 33 ms 6356 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 20 ms 6344 KB Output is correct
2 Correct 116 ms 45584 KB Output is correct
3 Correct 109 ms 45696 KB Output is correct
4 Correct 123 ms 45500 KB Output is correct
5 Correct 26 ms 6580 KB Output is correct
6 Correct 116 ms 42432 KB Output is correct
7 Correct 119 ms 42940 KB Output is correct
8 Correct 159 ms 43420 KB Output is correct
9 Correct 140 ms 43624 KB Output is correct
10 Correct 149 ms 46084 KB Output is correct
11 Correct 187 ms 45500 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 20 ms 6344 KB Output is correct
2 Correct 116 ms 45584 KB Output is correct
3 Correct 109 ms 45696 KB Output is correct
4 Correct 123 ms 45500 KB Output is correct
5 Correct 26 ms 6580 KB Output is correct
6 Correct 116 ms 42432 KB Output is correct
7 Correct 119 ms 42940 KB Output is correct
8 Correct 159 ms 43420 KB Output is correct
9 Correct 140 ms 43624 KB Output is correct
10 Correct 149 ms 46084 KB Output is correct
11 Correct 187 ms 45500 KB Output is correct
12 Incorrect 21 ms 6408 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 26 ms 6356 KB Output is correct
2 Correct 37 ms 7844 KB Output is correct
3 Correct 31 ms 8144 KB Output is correct
4 Correct 47 ms 7904 KB Output is correct
5 Correct 36 ms 7988 KB Output is correct
6 Correct 31 ms 8320 KB Output is correct
7 Correct 24 ms 6552 KB Output is correct
8 Correct 132 ms 42172 KB Output is correct
9 Correct 128 ms 42168 KB Output is correct
10 Correct 20 ms 6356 KB Output is correct
11 Correct 124 ms 45720 KB Output is correct
12 Correct 116 ms 45560 KB Output is correct
13 Correct 124 ms 45512 KB Output is correct
14 Correct 25 ms 6344 KB Output is correct
15 Correct 130 ms 42516 KB Output is correct
16 Correct 114 ms 42940 KB Output is correct
17 Correct 159 ms 43504 KB Output is correct
18 Correct 127 ms 43452 KB Output is correct
19 Correct 137 ms 46016 KB Output is correct
20 Correct 179 ms 45592 KB Output is correct
21 Correct 136 ms 42636 KB Output is correct
22 Correct 122 ms 42724 KB Output is correct
23 Correct 123 ms 42944 KB Output is correct
24 Correct 129 ms 42940 KB Output is correct
25 Correct 139 ms 43292 KB Output is correct
26 Correct 123 ms 42432 KB Output is correct
27 Correct 104 ms 42692 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 26 ms 6356 KB Output is correct
2 Correct 37 ms 7844 KB Output is correct
3 Correct 31 ms 8144 KB Output is correct
4 Correct 47 ms 7904 KB Output is correct
5 Correct 36 ms 7988 KB Output is correct
6 Correct 31 ms 8320 KB Output is correct
7 Correct 24 ms 6552 KB Output is correct
8 Correct 132 ms 42172 KB Output is correct
9 Correct 128 ms 42168 KB Output is correct
10 Correct 20 ms 6356 KB Output is correct
11 Correct 124 ms 45720 KB Output is correct
12 Correct 116 ms 45560 KB Output is correct
13 Correct 124 ms 45512 KB Output is correct
14 Correct 25 ms 6344 KB Output is correct
15 Correct 130 ms 42516 KB Output is correct
16 Correct 114 ms 42940 KB Output is correct
17 Correct 159 ms 43504 KB Output is correct
18 Correct 127 ms 43452 KB Output is correct
19 Correct 137 ms 46016 KB Output is correct
20 Correct 179 ms 45592 KB Output is correct
21 Correct 136 ms 42636 KB Output is correct
22 Correct 122 ms 42724 KB Output is correct
23 Correct 123 ms 42944 KB Output is correct
24 Correct 129 ms 42940 KB Output is correct
25 Correct 139 ms 43292 KB Output is correct
26 Correct 123 ms 42432 KB Output is correct
27 Correct 104 ms 42692 KB Output is correct
28 Incorrect 25 ms 6348 KB Extra information in the output file
29 Halted 0 ms 0 KB -