oj.uz

Submission #1039808

# Submission time Handle Problem Language Result Execution time Memory
1039808 2024-07-31T09:36:52 Z 12345678 Inside information (BOI21_servers) C++17
62.5 / 100
 3500 ms 43600 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
const int nx=250005, kx=18, mod=400;
 
int n, k, a[nx], b[nx], idx[nx], cnt[nx], lvl[nx], pa[nx][kx], up[nx], dn[nx], pw[nx], t, in[nx], out[nx], lst, dp[nx], l[nx], r[nx], pts[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; i++) pts[i]=i, dp[i]=1;
    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], idx[++cnt[i]]=i, d[a[i]].push_back({b[i], cnt[i]}), d[b[i]].push_back({a[i], cnt[i]}), l[cnt[i]+n]=pts[a[i]], r[cnt[i]+n]=pts[b[i]], pts[a[i]]=pts[b[i]]=cnt[i]+n;
        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]=='S')
        {
            if ((cnt[i]%mod)==0)
            {
                lst=cnt[i];
                for (int j=1; j<=n+cnt[j]; j++) dp[j]=1;
                for (int j=n+cnt[i]; j>=n+1; j--) dp[l[j]]+=dp[j], dp[r[j]]+=dp[j];
                lst=cnt[i];
            }
        }
        if (opr[i]=='Q') cout<<(query(i)?"yes\n":"no\n");
        if (opr[i]=='C') 
        {
            int tmp=dp[a[i]];
            for (int j=lst+1; j<=cnt[i]; j++) 
            {
                int f=1;
                b[i]=a[idx[j]];
                if (!query(i)) f=0;
                b[i]=b[idx[j]];
                if (!query(i)) f=0;
                tmp+=f;
            }
            cout<<tmp<<'\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 26 ms 18772 KB Output is correct
2 Correct 29 ms 19288 KB Output is correct
3 Correct 37 ms 19404 KB Output is correct
4 Correct 31 ms 19588 KB Output is correct
5 Correct 39 ms 19536 KB Output is correct
6 Correct 40 ms 19336 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 26 ms 18772 KB Output is correct
2 Correct 29 ms 19288 KB Output is correct
3 Correct 37 ms 19404 KB Output is correct
4 Correct 31 ms 19588 KB Output is correct
5 Correct 39 ms 19536 KB Output is correct
6 Correct 40 ms 19336 KB Output is correct
7 Correct 65 ms 18756 KB Output is correct
8 Incorrect 1526 ms 19024 KB Extra information in the output file
9 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 29 ms 18580 KB Output is correct
2 Correct 146 ms 36340 KB Output is correct
3 Correct 139 ms 36292 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 29 ms 18580 KB Output is correct
2 Correct 146 ms 36340 KB Output is correct
3 Correct 139 ms 36292 KB Output is correct
4 Correct 89 ms 18740 KB Output is correct
5 Correct 1057 ms 36256 KB Output is correct
6 Correct 1546 ms 35456 KB Output is correct
7 Correct 3385 ms 35628 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 18776 KB Output is correct
2 Correct 150 ms 43336 KB Output is correct
3 Correct 150 ms 43332 KB Output is correct
4 Correct 139 ms 43348 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 18776 KB Output is correct
2 Correct 150 ms 43336 KB Output is correct
3 Correct 150 ms 43332 KB Output is correct
4 Correct 139 ms 43348 KB Output is correct
5 Correct 42 ms 18768 KB Output is correct
6 Correct 2609 ms 42984 KB Output is correct
7 Correct 1326 ms 43324 KB Output is correct
8 Execution timed out 3522 ms 42392 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 18768 KB Output is correct
2 Correct 118 ms 36592 KB Output is correct
3 Correct 139 ms 35668 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 18768 KB Output is correct
2 Correct 118 ms 36592 KB Output is correct
3 Correct 139 ms 35668 KB Output is correct
4 Correct 66 ms 18756 KB Output is correct
5 Correct 3410 ms 35008 KB Output is correct
6 Correct 1690 ms 36608 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 20 ms 18780 KB Output is correct
2 Correct 168 ms 41976 KB Output is correct
3 Correct 141 ms 41836 KB Output is correct
4 Correct 138 ms 41812 KB Output is correct
5 Correct 24 ms 18780 KB Output is correct
6 Correct 114 ms 36692 KB Output is correct
7 Correct 143 ms 37204 KB Output is correct
8 Correct 182 ms 37552 KB Output is correct
9 Correct 139 ms 37660 KB Output is correct
10 Correct 155 ms 41296 KB Output is correct
11 Correct 161 ms 40784 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 20 ms 18780 KB Output is correct
2 Correct 168 ms 41976 KB Output is correct
3 Correct 141 ms 41836 KB Output is correct
4 Correct 138 ms 41812 KB Output is correct
5 Correct 24 ms 18780 KB Output is correct
6 Correct 114 ms 36692 KB Output is correct
7 Correct 143 ms 37204 KB Output is correct
8 Correct 182 ms 37552 KB Output is correct
9 Correct 139 ms 37660 KB Output is correct
10 Correct 155 ms 41296 KB Output is correct
11 Correct 161 ms 40784 KB Output is correct
12 Correct 42 ms 18772 KB Output is correct
13 Correct 2438 ms 41556 KB Output is correct
14 Correct 1272 ms 41552 KB Output is correct
15 Execution timed out 3591 ms 41040 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 26 ms 18776 KB Output is correct
2 Correct 33 ms 19472 KB Output is correct
3 Correct 38 ms 19540 KB Output is correct
4 Correct 40 ms 10584 KB Output is correct
5 Correct 30 ms 12776 KB Output is correct
6 Correct 41 ms 10576 KB Output is correct
7 Correct 28 ms 9564 KB Output is correct
8 Correct 194 ms 31712 KB Output is correct
9 Correct 160 ms 31400 KB Output is correct
10 Correct 33 ms 18652 KB Output is correct
11 Correct 155 ms 43600 KB Output is correct
12 Correct 178 ms 43344 KB Output is correct
13 Correct 161 ms 41332 KB Output is correct
14 Correct 25 ms 9448 KB Output is correct
15 Correct 139 ms 35232 KB Output is correct
16 Correct 152 ms 35668 KB Output is correct
17 Correct 162 ms 36028 KB Output is correct
18 Correct 190 ms 32596 KB Output is correct
19 Correct 172 ms 36436 KB Output is correct
20 Correct 205 ms 35992 KB Output is correct
21 Correct 159 ms 31796 KB Output is correct
22 Correct 157 ms 34848 KB Output is correct
23 Correct 156 ms 32340 KB Output is correct
24 Correct 153 ms 35472 KB Output is correct
25 Correct 196 ms 33748 KB Output is correct
26 Correct 143 ms 36540 KB Output is correct
27 Correct 169 ms 33840 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 26 ms 18776 KB Output is correct
2 Correct 33 ms 19472 KB Output is correct
3 Correct 38 ms 19540 KB Output is correct
4 Correct 40 ms 10584 KB Output is correct
5 Correct 30 ms 12776 KB Output is correct
6 Correct 41 ms 10576 KB Output is correct
7 Correct 28 ms 9564 KB Output is correct
8 Correct 194 ms 31712 KB Output is correct
9 Correct 160 ms 31400 KB Output is correct
10 Correct 33 ms 18652 KB Output is correct
11 Correct 155 ms 43600 KB Output is correct
12 Correct 178 ms 43344 KB Output is correct
13 Correct 161 ms 41332 KB Output is correct
14 Correct 25 ms 9448 KB Output is correct
15 Correct 139 ms 35232 KB Output is correct
16 Correct 152 ms 35668 KB Output is correct
17 Correct 162 ms 36028 KB Output is correct
18 Correct 190 ms 32596 KB Output is correct
19 Correct 172 ms 36436 KB Output is correct
20 Correct 205 ms 35992 KB Output is correct
21 Correct 159 ms 31796 KB Output is correct
22 Correct 157 ms 34848 KB Output is correct
23 Correct 156 ms 32340 KB Output is correct
24 Correct 153 ms 35472 KB Output is correct
25 Correct 196 ms 33748 KB Output is correct
26 Correct 143 ms 36540 KB Output is correct
27 Correct 169 ms 33840 KB Output is correct
28 Correct 66 ms 18772 KB Output is correct
29 Incorrect 1666 ms 19016 KB Extra information in the output file
30 Halted 0 ms 0 KB -