oj.uz

답안 #1026100

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1026100 2024-07-17T14:53:40 Z 12345678 Inside information (BOI21_servers) C++17
50 / 100
 125 ms 35668 KB 
#include <bits/stdc++.h>

using namespace std;

const int nx=250005, kx=18;

int n, k, a[nx], b[nx], cnt[nx], lvl[nx], pa[nx][kx], up[nx], dn[nx], pw[nx], t, in[nx], out[nx];
char opr[nx];
vector<pair<int, int>> d[nx];

void dfs(int u, int p)
{
    lvl[u]=lvl[p]+1;
    in[u]=++t;
    up[u]=p;
    if (pw[u]<pw[p]) up[u]=up[p];
    dn[u]=p;
    if (pw[u]>pw[p]) dn[u]=dn[p];
    pa[u][0]=p;
    for (int i=1; i<kx; i++) pa[u][i]=pa[pa[u][i-1]][i-1];
    for (auto [v, w]:d[u]) if (v!=p) pw[v]=w, dfs(v, u);
    out[u]=t;
}

pair<int, int> query1(int idx)
{
    //cout<<"query "<<a[idx]<<' '<<b[idx]<<'\n';
    if (in[a[idx]]<=in[b[idx]]&&in[b[idx]]<=out[a[idx]]) return {a[idx], 0};
    int tmp=a[idx];
    for (int i=kx-1; i>=0; i--) if (!(in[pa[tmp][i]]<=in[b[idx]]&&in[b[idx]]<=out[pa[tmp][i]])) tmp=pa[tmp][i];
    if (lvl[up[a[idx]]]>lvl[pa[tmp][0]]) return {-1, 0};
    return {pa[tmp][0], pw[tmp]};
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>k;
    for (int i=1; i<n+k; i++)
    {
        cin>>opr[i];
        cnt[i]=cnt[i-1];
        if (opr[i]=='S') cin>>a[i]>>b[i], cnt[i]++, d[a[i]].push_back({b[i], cnt[i]}), d[b[i]].push_back({a[i], cnt[i]});
        if (opr[i]=='Q') cin>>b[i]>>a[i];
        if (opr[i]=='C') cin>>a[i];
    }
    dfs(1, 1);
    //for (int i=1; i<=n; i++) cout<<"dfs "<<i<<' '<<up[i]<<' '<<dn[i]<<' '<<in[i]<<' '<<out[i]<<'\n';
    for (int i=1; i<n+k; i++)
    {
        if (opr[i]=='Q')
        {
            auto [u, lst]=query1(i);
            //cout<<"debug "<<i<<' '<<u<<' '<<lst<<'\n';
            if (u==-1) cout<<"no\n";
            else
            {
                if (u==b[i]&&lst<=cnt[i]) cout<<"yes\n";
                else if (u==b[i]&&lst>cnt[i]) cout<<"no\n";
                else
                {
                    int vl=pw[b[i]], tmp=b[i];
                    if (lvl[dn[b[i]]]>lvl[u]||pw[b[i]]>cnt[i]) cout<<"no\n";
                    else
                    {
                        for (int j=kx-1; j>=0; j--) if (lvl[pa[tmp][j]]>lvl[u]) tmp=pa[tmp][j];
                        if (lst<pw[tmp]) cout<<"yes\n";
                        else cout<<"no\n";
                    }
                }
            }
        }
        if (opr[i]=='C') cout<<0<<'\n';
    }
}

Compilation message

servers.cpp: In function 'int main()':
servers.cpp:62:25: warning: unused variable 'vl' [-Wunused-variable]
   62 |                     int vl=pw[b[i]], tmp=b[i];
      |                         ^~

Subtask #1
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 9052 KB Output is correct
2 Correct 31 ms 10208 KB Output is correct
3 Correct 38 ms 10120 KB Output is correct
4 Correct 36 ms 10324 KB Output is correct
5 Correct 39 ms 10412 KB Output is correct
6 Correct 41 ms 10232 KB Output is correct

Subtask #2
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 9052 KB Output is correct
2 Correct 31 ms 10208 KB Output is correct
3 Correct 38 ms 10120 KB Output is correct
4 Correct 36 ms 10324 KB Output is correct
5 Correct 39 ms 10412 KB Output is correct
6 Correct 41 ms 10232 KB Output is correct
7 Incorrect 32 ms 9128 KB Extra information in the output file
8 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 9144 KB Output is correct
2 Correct 93 ms 28612 KB Output is correct
3 Correct 86 ms 28488 KB Output is correct

Subtask #4
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 9144 KB Output is correct
2 Correct 93 ms 28612 KB Output is correct
3 Correct 86 ms 28488 KB Output is correct
4 Incorrect 30 ms 9044 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 9052 KB Output is correct
2 Correct 95 ms 35664 KB Output is correct
3 Correct 87 ms 35548 KB Output is correct
4 Correct 96 ms 35408 KB Output is correct

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 9052 KB Output is correct
2 Correct 95 ms 35664 KB Output is correct
3 Correct 87 ms 35548 KB Output is correct
4 Correct 96 ms 35408 KB Output is correct
5 Incorrect 20 ms 9044 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 9052 KB Output is correct
2 Correct 78 ms 29008 KB Output is correct
3 Correct 76 ms 29524 KB Output is correct

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 9052 KB Output is correct
2 Correct 78 ms 29008 KB Output is correct
3 Correct 76 ms 29524 KB Output is correct
4 Incorrect 25 ms 9044 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 9112 KB Output is correct
2 Correct 87 ms 35656 KB Output is correct
3 Correct 94 ms 35540 KB Output is correct
4 Correct 95 ms 35408 KB Output is correct
5 Correct 25 ms 9048 KB Output is correct
6 Correct 73 ms 28972 KB Output is correct
7 Correct 85 ms 29780 KB Output is correct
8 Correct 94 ms 29780 KB Output is correct
9 Correct 93 ms 29780 KB Output is correct
10 Correct 104 ms 33620 KB Output is correct
11 Correct 125 ms 33136 KB Output is correct

Subtask #10
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 9112 KB Output is correct
2 Correct 87 ms 35656 KB Output is correct
3 Correct 94 ms 35540 KB Output is correct
4 Correct 95 ms 35408 KB Output is correct
5 Correct 25 ms 9048 KB Output is correct
6 Correct 73 ms 28972 KB Output is correct
7 Correct 85 ms 29780 KB Output is correct
8 Correct 94 ms 29780 KB Output is correct
9 Correct 93 ms 29780 KB Output is correct
10 Correct 104 ms 33620 KB Output is correct
11 Correct 125 ms 33136 KB Output is correct
12 Incorrect 20 ms 9052 KB Extra information in the output file
13 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 9052 KB Output is correct
2 Correct 32 ms 10028 KB Output is correct
3 Correct 38 ms 10072 KB Output is correct
4 Correct 33 ms 10080 KB Output is correct
5 Correct 29 ms 10320 KB Output is correct
6 Correct 41 ms 10072 KB Output is correct
7 Correct 30 ms 9044 KB Output is correct
8 Correct 88 ms 28616 KB Output is correct
9 Correct 79 ms 28612 KB Output is correct
10 Correct 21 ms 9156 KB Output is correct
11 Correct 84 ms 35668 KB Output is correct
12 Correct 94 ms 35668 KB Output is correct
13 Correct 97 ms 35416 KB Output is correct
14 Correct 25 ms 9052 KB Output is correct
15 Correct 70 ms 29060 KB Output is correct
16 Correct 79 ms 29468 KB Output is correct
17 Correct 92 ms 29780 KB Output is correct
18 Correct 107 ms 29780 KB Output is correct
19 Correct 106 ms 33620 KB Output is correct
20 Correct 118 ms 33184 KB Output is correct
21 Correct 82 ms 28996 KB Output is correct
22 Correct 89 ms 29196 KB Output is correct
23 Correct 83 ms 29272 KB Output is correct
24 Correct 86 ms 29524 KB Output is correct
25 Correct 102 ms 30628 KB Output is correct
26 Correct 83 ms 29012 KB Output is correct
27 Correct 75 ms 28852 KB Output is correct

Subtask #12
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 9052 KB Output is correct
2 Correct 32 ms 10028 KB Output is correct
3 Correct 38 ms 10072 KB Output is correct
4 Correct 33 ms 10080 KB Output is correct
5 Correct 29 ms 10320 KB Output is correct
6 Correct 41 ms 10072 KB Output is correct
7 Correct 30 ms 9044 KB Output is correct
8 Correct 88 ms 28616 KB Output is correct
9 Correct 79 ms 28612 KB Output is correct
10 Correct 21 ms 9156 KB Output is correct
11 Correct 84 ms 35668 KB Output is correct
12 Correct 94 ms 35668 KB Output is correct
13 Correct 97 ms 35416 KB Output is correct
14 Correct 25 ms 9052 KB Output is correct
15 Correct 70 ms 29060 KB Output is correct
16 Correct 79 ms 29468 KB Output is correct
17 Correct 92 ms 29780 KB Output is correct
18 Correct 107 ms 29780 KB Output is correct
19 Correct 106 ms 33620 KB Output is correct
20 Correct 118 ms 33184 KB Output is correct
21 Correct 82 ms 28996 KB Output is correct
22 Correct 89 ms 29196 KB Output is correct
23 Correct 83 ms 29272 KB Output is correct
24 Correct 86 ms 29524 KB Output is correct
25 Correct 102 ms 30628 KB Output is correct
26 Correct 83 ms 29012 KB Output is correct
27 Correct 75 ms 28852 KB Output is correct
28 Incorrect 26 ms 8968 KB Extra information in the output file
29 Halted 0 ms 0 KB -