답안 #521093

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
521093	2022-01-31T17:44:04 Z	blue	Inside information (BOI21_servers)	C++17	67.5 / 100	3500 ms	32116 KB

servers

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

using vi = vector<int>;
using pii = pair<int, int>;
#define sz(x) int(x.size())

const int mx = 120'000;




struct edge
{
    int v;
    int t;
};

vector<edge> S[1+mx];





struct query
{
    int a;
    int t;
};

vector<query> Q[1+mx]; //stored by d





vector<int> C[1+mx]; //stored by d



int N, K;

vi res(2*mx + 5);












vi banned(1+mx, 0);

vi st_count(1+mx, 0);

vi lst;




void dfs(int u, int p)
{
    lst.push_back(u);

    st_count[u] = 1;
    for(auto e: S[u])
    {
        int v = e.v;
        if(v == p) continue;

        if(banned[v]) continue;

        dfs(v, u);
        st_count[u] += st_count[v];
    }
}


vi out_good(1+mx); //going out from centroid
vi in_good(1+mx); //coming in to centroid
vi root_time(1+mx);
vi par_time(1+mx);


vi st_index(1+mx);

vi exists(1+mx, 0);



void dfs2(int u, int p)
{
    for(auto e: S[u])
    {
        int v = e.v;
        int t = e.t;

        if(v == p) continue;

        if(banned[v]) continue;

        root_time[v] = root_time[u];
        par_time[v] = t;

        out_good[v] = out_good[u] && (par_time[v] > par_time[u]);
        in_good[v] = in_good[u] && (par_time[v] < par_time[u]);

        st_index[v] = st_index[u];

        dfs2(v, u);
    }
}


vector<pii> obj_list;


void solve(int src)
{
    lst.clear();

    dfs(src, src);

    int cent = -1;


    for(int u: lst)
    {
        exists[u] = 1;

        if(2 * st_count[u] < st_count[src]) continue;

        if(cent == -1) cent = u;
        else if(st_count[u] < st_count[cent]) cent = u;
    }


    // cerr << "\n\n\n\n";
    // for(int l: lst) cerr << l << ' ';
    // cerr << ": centroid = " << cent << '\n';

    // for(int l: lst) cerr << l << " : " << out_good[l] << ' ' << in_good[l] << ' ' << root_time[l] << ' ' << par_time[l] << '\n';


    int stid = 0;
    st_index[cent] = 0;

    for(auto e: S[cent])
    {
        int v = e.v;
        int t = e.t;

        if(banned[v]) continue;

        st_index[v] = ++stid;
        in_good[v] = out_good[v] = 1;
        root_time[v] = par_time[v] = t;

        dfs2(v, cent);
    }



    for(int d: lst)
    {
        for(query qr: Q[d])
        {
            int a = qr.a;
            int t = qr.t;

            if(!exists[a]) continue;

            if(d == cent)
            {
                if(a == cent)
                    res[t] = 1;
                else 
                    res[t] |= (out_good[a] && par_time[a] < t);
            }
            else
            {
                if(a == cent)
                    res[t] |= (in_good[d] && root_time[d] < t);
                else
                    res[t] |= (in_good[d] && out_good[a] && root_time[d] < root_time[a] && par_time[a] < t);
            }
        }
    }



    vi alist;
    for(int a: lst)
    {
        if(a == cent || out_good[a]) 
            {
                alist.push_back(a);
                // cerr << "pushing " << a << '\n';
            }
    }

    for(int d: lst)
    {
        if(d == cent)
        {
            for(int t: C[d])
            {
                for(int a: alist)
                    res[t] += (a == cent || par_time[a] < t);
            }
        }
        else 
        {
            if(!in_good[d]) continue;

            for(int t: C[d])
            {
                if(t < root_time[d]) continue;

                for(int a: alist)
                    res[t] += (a == cent || (par_time[a] < t && root_time[a] > root_time[d]));
            }
        }
    }





    for(int u: lst) exists[u] = 0;

    banned[cent] = 1;

    for(auto e: S[cent])
    {
        if(banned[e.v]) continue;
        solve(e.v);
    }


    banned[cent] = 0;

    
}




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

    cin >> N >> K;

    char c[N+K];

    for(int q = 1; q <= N+K-1; q++)
    {
        cin >> c[q];
        if(c[q] == 'S')
        {
            int a, b;
            cin >> a >> b;
            S[a].push_back({b, q});
            S[b].push_back({a, q});
        }
        else if(c[q] == 'Q')
        {
            int a, d;
            cin >> a >> d;
            Q[d].push_back({a, q});
        }
        else
        {
            int d;
            cin >> d;

            C[d].push_back(q);
        }
    }




    solve(1);




    for(int q = 1; q <= N+K-1; q++)
    {
        if(c[q] == 'S') continue;
        else if(c[q] == 'Q')
        {
            if(res[q] == 1) cout << "yes\n";
            else cout << "no\n";
        }
        else cout << res[q] << '\n';
    }
}

Subtask #1
2.5 / 2.5

#	결과	실행 시간	메모리	Grader output
1	Correct	41 ms	15448 KB	Output is correct
2	Correct	57 ms	15692 KB	Output is correct
3	Correct	53 ms	15580 KB	Output is correct
4	Correct	50 ms	15808 KB	Output is correct
5	Correct	39 ms	16016 KB	Output is correct
6	Correct	43 ms	15864 KB	Output is correct

Subtask #2
2.5 / 2.5

#	결과	실행 시간	메모리	Grader output
1	Correct	41 ms	15448 KB	Output is correct
2	Correct	57 ms	15692 KB	Output is correct
3	Correct	53 ms	15580 KB	Output is correct
4	Correct	50 ms	15808 KB	Output is correct
5	Correct	39 ms	16016 KB	Output is correct
6	Correct	43 ms	15864 KB	Output is correct
7	Correct	35 ms	15436 KB	Output is correct
8	Correct	50 ms	15348 KB	Output is correct
9	Correct	108 ms	15248 KB	Output is correct
10	Correct	57 ms	15404 KB	Output is correct
11	Correct	66 ms	15636 KB	Output is correct
12	Correct	342 ms	15332 KB	Output is correct

Subtask #3
2.5 / 2.5

#	결과	실행 시간	메모리	Grader output
1	Correct	26 ms	15456 KB	Output is correct
2	Correct	133 ms	22444 KB	Output is correct
3	Correct	149 ms	22988 KB	Output is correct

Subtask #4
0 / 2.5

#	결과	실행 시간	메모리	Grader output
1	Correct	26 ms	15456 KB	Output is correct
2	Correct	133 ms	22444 KB	Output is correct
3	Correct	149 ms	22988 KB	Output is correct
4	Correct	39 ms	15856 KB	Output is correct
5	Execution timed out	3552 ms	24608 KB	Time limit exceeded
6	Halted	0 ms	0 KB	-

Subtask #5
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	27 ms	15492 KB	Output is correct
2	Correct	328 ms	28384 KB	Output is correct
3	Correct	373 ms	28952 KB	Output is correct
4	Correct	212 ms	29096 KB	Output is correct

Subtask #6
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	27 ms	15492 KB	Output is correct
2	Correct	328 ms	28384 KB	Output is correct
3	Correct	373 ms	28952 KB	Output is correct
4	Correct	212 ms	29096 KB	Output is correct
5	Correct	29 ms	15812 KB	Output is correct
6	Correct	343 ms	31736 KB	Output is correct
7	Correct	2149 ms	32116 KB	Output is correct
8	Correct	316 ms	30920 KB	Output is correct
9	Correct	299 ms	30964 KB	Output is correct

Subtask #7
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	35 ms	15552 KB	Output is correct
2	Correct	218 ms	22112 KB	Output is correct
3	Correct	309 ms	22384 KB	Output is correct

Subtask #8
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	35 ms	15552 KB	Output is correct
2	Correct	218 ms	22112 KB	Output is correct
3	Correct	309 ms	22384 KB	Output is correct
4	Correct	28 ms	15788 KB	Output is correct
5	Correct	2283 ms	25504 KB	Output is correct
6	Correct	281 ms	25068 KB	Output is correct

Subtask #9
12.5 / 12.5

#	결과	실행 시간	메모리	Grader output
1	Correct	29 ms	15548 KB	Output is correct
2	Correct	383 ms	28376 KB	Output is correct
3	Correct	338 ms	28896 KB	Output is correct
4	Correct	279 ms	29096 KB	Output is correct
5	Correct	26 ms	16076 KB	Output is correct
6	Correct	202 ms	22608 KB	Output is correct
7	Correct	347 ms	22392 KB	Output is correct
8	Correct	336 ms	23096 KB	Output is correct
9	Correct	381 ms	23040 KB	Output is correct
10	Correct	414 ms	26044 KB	Output is correct
11	Correct	363 ms	24924 KB	Output is correct

Subtask #10
0 / 12.5

#	결과	실행 시간	메모리	Grader output
1	Correct	29 ms	15548 KB	Output is correct
2	Correct	383 ms	28376 KB	Output is correct
3	Correct	338 ms	28896 KB	Output is correct
4	Correct	279 ms	29096 KB	Output is correct
5	Correct	26 ms	16076 KB	Output is correct
6	Correct	202 ms	22608 KB	Output is correct
7	Correct	347 ms	22392 KB	Output is correct
8	Correct	336 ms	23096 KB	Output is correct
9	Correct	381 ms	23040 KB	Output is correct
10	Correct	414 ms	26044 KB	Output is correct
11	Correct	363 ms	24924 KB	Output is correct
12	Correct	29 ms	15776 KB	Output is correct
13	Correct	357 ms	31740 KB	Output is correct
14	Correct	2237 ms	32104 KB	Output is correct
15	Correct	332 ms	30904 KB	Output is correct
16	Correct	308 ms	30856 KB	Output is correct
17	Correct	28 ms	16344 KB	Output is correct
18	Correct	2164 ms	25552 KB	Output is correct
19	Correct	269 ms	25152 KB	Output is correct
20	Correct	316 ms	26028 KB	Output is correct
21	Correct	328 ms	25944 KB	Output is correct
22	Correct	1298 ms	27396 KB	Output is correct
23	Execution timed out	3529 ms	28116 KB	Time limit exceeded
24	Halted	0 ms	0 KB	-

Subtask #11
17.5 / 17.5

#	결과	실행 시간	메모리	Grader output
1	Correct	37 ms	15456 KB	Output is correct
2	Correct	36 ms	15772 KB	Output is correct
3	Correct	38 ms	15564 KB	Output is correct
4	Correct	45 ms	15852 KB	Output is correct
5	Correct	41 ms	15992 KB	Output is correct
6	Correct	33 ms	15796 KB	Output is correct
7	Correct	25 ms	15512 KB	Output is correct
8	Correct	134 ms	22516 KB	Output is correct
9	Correct	156 ms	22956 KB	Output is correct
10	Correct	27 ms	16068 KB	Output is correct
11	Correct	320 ms	28944 KB	Output is correct
12	Correct	355 ms	28892 KB	Output is correct
13	Correct	229 ms	29044 KB	Output is correct
14	Correct	27 ms	16052 KB	Output is correct
15	Correct	240 ms	22592 KB	Output is correct
16	Correct	306 ms	22376 KB	Output is correct
17	Correct	337 ms	23096 KB	Output is correct
18	Correct	331 ms	23036 KB	Output is correct
19	Correct	429 ms	26216 KB	Output is correct
20	Correct	347 ms	24916 KB	Output is correct
21	Correct	173 ms	22440 KB	Output is correct
22	Correct	158 ms	22252 KB	Output is correct
23	Correct	271 ms	22684 KB	Output is correct
24	Correct	232 ms	22636 KB	Output is correct
25	Correct	391 ms	25540 KB	Output is correct
26	Correct	300 ms	21468 KB	Output is correct
27	Correct	266 ms	21420 KB	Output is correct

Subtask #12
0 / 17.5

#	결과	실행 시간	메모리	Grader output
1	Correct	37 ms	15456 KB	Output is correct
2	Correct	36 ms	15772 KB	Output is correct
3	Correct	38 ms	15564 KB	Output is correct
4	Correct	45 ms	15852 KB	Output is correct
5	Correct	41 ms	15992 KB	Output is correct
6	Correct	33 ms	15796 KB	Output is correct
7	Correct	25 ms	15512 KB	Output is correct
8	Correct	134 ms	22516 KB	Output is correct
9	Correct	156 ms	22956 KB	Output is correct
10	Correct	27 ms	16068 KB	Output is correct
11	Correct	320 ms	28944 KB	Output is correct
12	Correct	355 ms	28892 KB	Output is correct
13	Correct	229 ms	29044 KB	Output is correct
14	Correct	27 ms	16052 KB	Output is correct
15	Correct	240 ms	22592 KB	Output is correct
16	Correct	306 ms	22376 KB	Output is correct
17	Correct	337 ms	23096 KB	Output is correct
18	Correct	331 ms	23036 KB	Output is correct
19	Correct	429 ms	26216 KB	Output is correct
20	Correct	347 ms	24916 KB	Output is correct
21	Correct	173 ms	22440 KB	Output is correct
22	Correct	158 ms	22252 KB	Output is correct
23	Correct	271 ms	22684 KB	Output is correct
24	Correct	232 ms	22636 KB	Output is correct
25	Correct	391 ms	25540 KB	Output is correct
26	Correct	300 ms	21468 KB	Output is correct
27	Correct	266 ms	21420 KB	Output is correct
28	Correct	28 ms	15860 KB	Output is correct
29	Correct	50 ms	16432 KB	Output is correct
30	Correct	111 ms	16288 KB	Output is correct
31	Correct	41 ms	16564 KB	Output is correct
32	Correct	39 ms	16692 KB	Output is correct
33	Correct	342 ms	16428 KB	Output is correct
34	Correct	27 ms	16384 KB	Output is correct
35	Execution timed out	3530 ms	24532 KB	Time limit exceeded
36	Halted	0 ms	0 KB	-

답안 #521093

Compilation message