oj.uz

Submission #1039623

# Submission time Handle Problem Language Result Execution time Memory
1039623 2024-07-31T06:05:43 Z 12345678 Inside information (BOI21_servers) C++17
50 / 100
 106 ms 37260 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)
{
    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 query(int i)
{
    auto [u, lst]=query1(i);
    if (u==-1) return 0;
    else
    {
        if (u==b[i]&&lst<=cnt[i]) return 1;
        else if (u==b[i]&&lst>cnt[i]) return 0;
        else
        {
            int vl=pw[b[i]], tmp=b[i];
            if (lvl[dn[b[i]]]>lvl[u]||pw[b[i]]>cnt[i]) return 0;
            else
            {
                for (int j=kx-1; j>=0; j--) if (lvl[pa[tmp][j]]>lvl[u]) tmp=pa[tmp][j];
                if (lst<pw[tmp]) return 1;
                else return 0;
            }
        }
    }
}

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+k; i++)
    {
        if (opr[i]=='Q') cout<<(query(i)?"yes\n":"no\n");
        if (opr[i]=='C') cout<<0<<'\n';
    }
}

Compilation message

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

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 25 ms 13400 KB Output is correct
2 Correct 29 ms 14112 KB Output is correct
3 Correct 36 ms 14160 KB Output is correct
4 Correct 31 ms 14420 KB Output is correct
5 Correct 34 ms 14420 KB Output is correct
6 Correct 38 ms 14168 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 25 ms 13400 KB Output is correct
2 Correct 29 ms 14112 KB Output is correct
3 Correct 36 ms 14160 KB Output is correct
4 Correct 31 ms 14420 KB Output is correct
5 Correct 34 ms 14420 KB Output is correct
6 Correct 38 ms 14168 KB Output is correct
7 Incorrect 27 ms 13408 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 33 ms 13404 KB Output is correct
2 Correct 77 ms 30148 KB Output is correct
3 Correct 74 ms 30148 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 33 ms 13404 KB Output is correct
2 Correct 77 ms 30148 KB Output is correct
3 Correct 74 ms 30148 KB Output is correct
4 Incorrect 30 ms 13404 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 21 ms 13404 KB Output is correct
2 Correct 76 ms 37204 KB Output is correct
3 Correct 97 ms 37200 KB Output is correct
4 Correct 95 ms 37148 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 13404 KB Output is correct
2 Correct 76 ms 37204 KB Output is correct
3 Correct 97 ms 37200 KB Output is correct
4 Correct 95 ms 37148 KB Output is correct
5 Incorrect 18 ms 13404 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 29 ms 13464 KB Output is correct
2 Correct 64 ms 30544 KB Output is correct
3 Correct 72 ms 32080 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 13464 KB Output is correct
2 Correct 64 ms 30544 KB Output is correct
3 Correct 72 ms 32080 KB Output is correct
4 Incorrect 23 ms 13400 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 13400 KB Output is correct
2 Correct 82 ms 37076 KB Output is correct
3 Correct 81 ms 37260 KB Output is correct
4 Correct 98 ms 36976 KB Output is correct
5 Correct 23 ms 13404 KB Output is correct
6 Correct 62 ms 30544 KB Output is correct
7 Correct 77 ms 32080 KB Output is correct
8 Correct 80 ms 31244 KB Output is correct
9 Correct 82 ms 31328 KB Output is correct
10 Correct 94 ms 35228 KB Output is correct
11 Correct 106 ms 34748 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 21 ms 13400 KB Output is correct
2 Correct 82 ms 37076 KB Output is correct
3 Correct 81 ms 37260 KB Output is correct
4 Correct 98 ms 36976 KB Output is correct
5 Correct 23 ms 13404 KB Output is correct
6 Correct 62 ms 30544 KB Output is correct
7 Correct 77 ms 32080 KB Output is correct
8 Correct 80 ms 31244 KB Output is correct
9 Correct 82 ms 31328 KB Output is correct
10 Correct 94 ms 35228 KB Output is correct
11 Correct 106 ms 34748 KB Output is correct
12 Incorrect 21 ms 13404 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 24 ms 13404 KB Output is correct
2 Correct 30 ms 14248 KB Output is correct
3 Correct 36 ms 14172 KB Output is correct
4 Correct 31 ms 14420 KB Output is correct
5 Correct 34 ms 14420 KB Output is correct
6 Correct 39 ms 14176 KB Output is correct
7 Correct 28 ms 13392 KB Output is correct
8 Correct 71 ms 30156 KB Output is correct
9 Correct 76 ms 30148 KB Output is correct
10 Correct 19 ms 13656 KB Output is correct
11 Correct 78 ms 37140 KB Output is correct
12 Correct 91 ms 37204 KB Output is correct
13 Correct 87 ms 37096 KB Output is correct
14 Correct 24 ms 13476 KB Output is correct
15 Correct 62 ms 30544 KB Output is correct
16 Correct 73 ms 32112 KB Output is correct
17 Correct 82 ms 31356 KB Output is correct
18 Correct 77 ms 31252 KB Output is correct
19 Correct 95 ms 35560 KB Output is correct
20 Correct 102 ms 34616 KB Output is correct
21 Correct 79 ms 31708 KB Output is correct
22 Correct 75 ms 31932 KB Output is correct
23 Correct 75 ms 32016 KB Output is correct
24 Correct 86 ms 32340 KB Output is correct
25 Correct 87 ms 32200 KB Output is correct
26 Correct 70 ms 31572 KB Output is correct
27 Correct 71 ms 30452 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 24 ms 13404 KB Output is correct
2 Correct 30 ms 14248 KB Output is correct
3 Correct 36 ms 14172 KB Output is correct
4 Correct 31 ms 14420 KB Output is correct
5 Correct 34 ms 14420 KB Output is correct
6 Correct 39 ms 14176 KB Output is correct
7 Correct 28 ms 13392 KB Output is correct
8 Correct 71 ms 30156 KB Output is correct
9 Correct 76 ms 30148 KB Output is correct
10 Correct 19 ms 13656 KB Output is correct
11 Correct 78 ms 37140 KB Output is correct
12 Correct 91 ms 37204 KB Output is correct
13 Correct 87 ms 37096 KB Output is correct
14 Correct 24 ms 13476 KB Output is correct
15 Correct 62 ms 30544 KB Output is correct
16 Correct 73 ms 32112 KB Output is correct
17 Correct 82 ms 31356 KB Output is correct
18 Correct 77 ms 31252 KB Output is correct
19 Correct 95 ms 35560 KB Output is correct
20 Correct 102 ms 34616 KB Output is correct
21 Correct 79 ms 31708 KB Output is correct
22 Correct 75 ms 31932 KB Output is correct
23 Correct 75 ms 32016 KB Output is correct
24 Correct 86 ms 32340 KB Output is correct
25 Correct 87 ms 32200 KB Output is correct
26 Correct 70 ms 31572 KB Output is correct
27 Correct 71 ms 30452 KB Output is correct
28 Incorrect 24 ms 13400 KB Extra information in the output file
29 Halted 0 ms 0 KB -