답안 #554426

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
554426	2022-04-28T11:29:20 Z	Jarif_Rahman	Inside information (BOI21_servers)	C++17	50 / 100	578 ms	24028 KB

servers

#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

int n, q;
vector<vector<pair<int, int>>> v;
vector<int> sz;
vector<vector<pair<int, int>>> queires;
vector<bool> marked, ans;
vector<int> qa;

vector<bool> isdec, isinc;
vector<int> mx, mn;
vector<int> centroid_id, anc_id;

void pre_centroid(int nd, int ss){
    sz[nd] = 1;
    isdec[nd] = 1;
    isinc[nd] = 1;
    mx[nd] = -1;
    mn[nd] = q+1;
    for(auto [x, w]: v[nd]) if(x != ss && !marked[x]) pre_centroid(x, nd);
    for(auto [x, w]: v[nd]) if(x != ss && !marked[x]) sz[nd]+=sz[x];
}

int centroid(int nd, int ss, int total){
    int mx = 0;
    for(auto [x, w]: v[nd]) if(x != ss && !marked[x]) mx = max(mx, sz[x]);
    if(mx <= total/2 && total-sz[nd] <= total/2) return nd;
    for(auto [x, w]: v[nd]) if(x != ss && !marked[x]){
        int cur = centroid(x, nd, total);
        if(cur != -1) return cur;
    }
    return -1;
}

void dfs1(int nd, int ss, int anc, int _mx, int _mn, bool isDec, bool isInc){
    isdec[nd] = isDec;
    isinc[nd] = isInc;
    mx[nd] = _mx;
    mn[nd] = _mn;
    anc_id[nd] = anc;

    centroid_id[nd] = (ss == -1?nd:centroid_id[ss]);

    for(auto [x, w]: v[nd]) if(x != ss && !marked[x]){
        dfs1(x, nd, anc==-1?x:anc, max(_mx, w), min(_mn, w), isDec & (w < _mn), isInc & (w > _mx));
    }
}

void dfs2(int nd, int ss){
    for(auto [in, d]: queires[nd]){
        if(d == -1){
            if(!isdec[nd]) continue;
            continue;
        }
        if(centroid_id[d] != centroid_id[nd]) continue;
        if(anc_id[nd] == anc_id[d]) continue;
        if(in <= max(mx[d], mx[nd])) continue;
        if(!isdec[d]) continue;
        if(!isinc[nd]) continue;
        if(mx[d] >= mn[nd]) continue;
        ans[qa[in]] = 1;
    }
    for(auto [x, w]: v[nd]) if(x != ss && !marked[x]) dfs2(x, nd);
}

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

    cin >> n >> q; q+=n-1;

    v.assign(n, {});
    sz.assign(n, 1);
    queires.assign(n, {});
    marked.assign(n, 0);
    qa.assign(q, -1);

    isdec.assign(n, 1);
    isinc.assign(n, 1);
    mx.assign(n, -1);
    mn.assign(n, q+1);
    centroid_id.assign(n, -1);
    anc_id.assign(n, -1);

    for(int i = 0; i < q; i++){
        char tt; int a, b; cin >> tt >> a;;
        if(tt != 'C') cin >> b;
        a--, b--;
        if(tt == 'S'){
            v[a].pb({b, i});
            v[b].pb({a, i});
        }
        else if(tt == 'Q'){
            queires[a].pb({i, b});
            qa[i] = ans.size();
            ans.pb(a == b);
        }
        else{
            queires[a].pb({i, -1});
        }
    }

    queue<int> Q;
    Q.push(0);

    while(!Q.empty()){
        int x = Q.front();
        Q.pop();
        pre_centroid(x, -1);
        int c = centroid(x, -1, sz[x]);

        dfs1(c, -1, -1, -1, q+1, 1, 1);
        dfs2(c, -1);

        marked[c] = 1;
        for(auto [x, w]: v[c]) if(!marked[x]) Q.push(x);
    }

    for(auto bl: ans) cout << (bl?"yes\n":"no\n");
}

Subtask #1
2.5 / 2.5

#	결과	실행 시간	메모리	Grader output
1	Correct	20 ms	2764 KB	Output is correct
2	Correct	35 ms	3168 KB	Output is correct
3	Correct	31 ms	3024 KB	Output is correct
4	Correct	39 ms	3268 KB	Output is correct
5	Correct	39 ms	3456 KB	Output is correct
6	Correct	31 ms	3216 KB	Output is correct

Subtask #2
0 / 2.5

#	결과	실행 시간	메모리	Grader output
1	Correct	20 ms	2764 KB	Output is correct
2	Correct	35 ms	3168 KB	Output is correct
3	Correct	31 ms	3024 KB	Output is correct
4	Correct	39 ms	3268 KB	Output is correct
5	Correct	39 ms	3456 KB	Output is correct
6	Correct	31 ms	3216 KB	Output is correct
7	Incorrect	25 ms	3324 KB	Extra information in the output file
8	Halted	0 ms	0 KB	-

Subtask #3
2.5 / 2.5

#	결과	실행 시간	메모리	Grader output
1	Correct	22 ms	2764 KB	Output is correct
2	Correct	156 ms	17172 KB	Output is correct
3	Correct	163 ms	17148 KB	Output is correct

Subtask #4
0 / 2.5

#	결과	실행 시간	메모리	Grader output
1	Correct	22 ms	2764 KB	Output is correct
2	Correct	156 ms	17172 KB	Output is correct
3	Correct	163 ms	17148 KB	Output is correct
4	Incorrect	25 ms	3452 KB	Extra information in the output file
5	Halted	0 ms	0 KB	-

Subtask #5
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	23 ms	2704 KB	Output is correct
2	Correct	502 ms	23636 KB	Output is correct
3	Correct	446 ms	23728 KB	Output is correct
4	Correct	246 ms	23372 KB	Output is correct

Subtask #6
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	23 ms	2704 KB	Output is correct
2	Correct	502 ms	23636 KB	Output is correct
3	Correct	446 ms	23728 KB	Output is correct
4	Correct	246 ms	23372 KB	Output is correct
5	Incorrect	20 ms	3332 KB	Extra information in the output file
6	Halted	0 ms	0 KB	-

Subtask #7
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	22 ms	2784 KB	Output is correct
2	Correct	265 ms	17136 KB	Output is correct
3	Correct	359 ms	17100 KB	Output is correct

Subtask #8
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	22 ms	2784 KB	Output is correct
2	Correct	265 ms	17136 KB	Output is correct
3	Correct	359 ms	17100 KB	Output is correct
4	Incorrect	24 ms	3396 KB	Extra information in the output file
5	Halted	0 ms	0 KB	-

Subtask #9
12.5 / 12.5

#	결과	실행 시간	메모리	Grader output
1	Correct	26 ms	2820 KB	Output is correct
2	Correct	447 ms	23620 KB	Output is correct
3	Correct	468 ms	23664 KB	Output is correct
4	Correct	252 ms	23468 KB	Output is correct
5	Correct	19 ms	2796 KB	Output is correct
6	Correct	243 ms	17124 KB	Output is correct
7	Correct	353 ms	17128 KB	Output is correct
8	Correct	402 ms	17832 KB	Output is correct
9	Correct	442 ms	17668 KB	Output is correct
10	Correct	511 ms	21724 KB	Output is correct
11	Correct	469 ms	21160 KB	Output is correct

Subtask #10
0 / 12.5

#	결과	실행 시간	메모리	Grader output
1	Correct	26 ms	2820 KB	Output is correct
2	Correct	447 ms	23620 KB	Output is correct
3	Correct	468 ms	23664 KB	Output is correct
4	Correct	252 ms	23468 KB	Output is correct
5	Correct	19 ms	2796 KB	Output is correct
6	Correct	243 ms	17124 KB	Output is correct
7	Correct	353 ms	17128 KB	Output is correct
8	Correct	402 ms	17832 KB	Output is correct
9	Correct	442 ms	17668 KB	Output is correct
10	Correct	511 ms	21724 KB	Output is correct
11	Correct	469 ms	21160 KB	Output is correct
12	Incorrect	21 ms	3412 KB	Extra information in the output file
13	Halted	0 ms	0 KB	-

Subtask #11
17.5 / 17.5

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	2820 KB	Output is correct
2	Correct	33 ms	3136 KB	Output is correct
3	Correct	32 ms	3072 KB	Output is correct
4	Correct	34 ms	3248 KB	Output is correct
5	Correct	35 ms	3532 KB	Output is correct
6	Correct	28 ms	3240 KB	Output is correct
7	Correct	21 ms	2764 KB	Output is correct
8	Correct	134 ms	17156 KB	Output is correct
9	Correct	129 ms	17160 KB	Output is correct
10	Correct	19 ms	2764 KB	Output is correct
11	Correct	431 ms	23720 KB	Output is correct
12	Correct	480 ms	23632 KB	Output is correct
13	Correct	279 ms	23388 KB	Output is correct
14	Correct	31 ms	2684 KB	Output is correct
15	Correct	302 ms	17100 KB	Output is correct
16	Correct	468 ms	17116 KB	Output is correct
17	Correct	501 ms	17776 KB	Output is correct
18	Correct	537 ms	17668 KB	Output is correct
19	Correct	570 ms	21732 KB	Output is correct
20	Correct	578 ms	21032 KB	Output is correct
21	Correct	214 ms	17080 KB	Output is correct
22	Correct	194 ms	17028 KB	Output is correct
23	Correct	340 ms	17244 KB	Output is correct
24	Correct	320 ms	17272 KB	Output is correct
25	Correct	577 ms	24028 KB	Output is correct
26	Correct	411 ms	16024 KB	Output is correct
27	Correct	461 ms	16024 KB	Output is correct

Subtask #12
0 / 17.5

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	2820 KB	Output is correct
2	Correct	33 ms	3136 KB	Output is correct
3	Correct	32 ms	3072 KB	Output is correct
4	Correct	34 ms	3248 KB	Output is correct
5	Correct	35 ms	3532 KB	Output is correct
6	Correct	28 ms	3240 KB	Output is correct
7	Correct	21 ms	2764 KB	Output is correct
8	Correct	134 ms	17156 KB	Output is correct
9	Correct	129 ms	17160 KB	Output is correct
10	Correct	19 ms	2764 KB	Output is correct
11	Correct	431 ms	23720 KB	Output is correct
12	Correct	480 ms	23632 KB	Output is correct
13	Correct	279 ms	23388 KB	Output is correct
14	Correct	31 ms	2684 KB	Output is correct
15	Correct	302 ms	17100 KB	Output is correct
16	Correct	468 ms	17116 KB	Output is correct
17	Correct	501 ms	17776 KB	Output is correct
18	Correct	537 ms	17668 KB	Output is correct
19	Correct	570 ms	21732 KB	Output is correct
20	Correct	578 ms	21032 KB	Output is correct
21	Correct	214 ms	17080 KB	Output is correct
22	Correct	194 ms	17028 KB	Output is correct
23	Correct	340 ms	17244 KB	Output is correct
24	Correct	320 ms	17272 KB	Output is correct
25	Correct	577 ms	24028 KB	Output is correct
26	Correct	411 ms	16024 KB	Output is correct
27	Correct	461 ms	16024 KB	Output is correct
28	Incorrect	32 ms	3324 KB	Extra information in the output file
29	Halted	0 ms	0 KB	-

답안 #554426

Compilation message