oj.uz

Submission #1040403

# Submission time Handle Problem Language Result Execution time Memory
1040403 2024-08-01T03:28:12 Z 12345678 Inside information (BOI21_servers) C++17
62.5 / 100
 3500 ms 46960 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

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)
            {
                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:47:17: warning: unused variable 'vl' [-Wunused-variable]
   47 |             int vl=pw[b[i]], tmp=b[i];
      |                 ^~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 21 ms 20828 KB Output is correct
2 Correct 25 ms 21332 KB Output is correct
3 Correct 31 ms 21472 KB Output is correct
4 Correct 27 ms 21596 KB Output is correct
5 Correct 23 ms 21636 KB Output is correct
6 Correct 33 ms 21584 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 21 ms 20828 KB Output is correct
2 Correct 25 ms 21332 KB Output is correct
3 Correct 31 ms 21472 KB Output is correct
4 Correct 27 ms 21596 KB Output is correct
5 Correct 23 ms 21636 KB Output is correct
6 Correct 33 ms 21584 KB Output is correct
7 Correct 56 ms 20812 KB Output is correct
8 Incorrect 1364 ms 21076 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 26 ms 20828 KB Output is correct
2 Correct 119 ms 37832 KB Output is correct
3 Correct 118 ms 37828 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 26 ms 20828 KB Output is correct
2 Correct 119 ms 37832 KB Output is correct
3 Correct 118 ms 37828 KB Output is correct
4 Correct 69 ms 20820 KB Output is correct
5 Correct 911 ms 37704 KB Output is correct
6 Correct 1309 ms 37060 KB Output is correct
7 Correct 2804 ms 37064 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 20820 KB Output is correct
2 Correct 121 ms 46960 KB Output is correct
3 Correct 123 ms 46672 KB Output is correct
4 Correct 126 ms 46744 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 20820 KB Output is correct
2 Correct 121 ms 46960 KB Output is correct
3 Correct 123 ms 46672 KB Output is correct
4 Correct 126 ms 46744 KB Output is correct
5 Correct 34 ms 20568 KB Output is correct
6 Correct 2100 ms 46432 KB Output is correct
7 Correct 1103 ms 46420 KB Output is correct
8 Execution timed out 3532 ms 45908 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 20816 KB Output is correct
2 Correct 101 ms 38228 KB Output is correct
3 Correct 123 ms 38688 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 20816 KB Output is correct
2 Correct 101 ms 38228 KB Output is correct
3 Correct 123 ms 38688 KB Output is correct
4 Correct 52 ms 20804 KB Output is correct
5 Correct 2924 ms 37968 KB Output is correct
6 Correct 1447 ms 38224 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 20 ms 20816 KB Output is correct
2 Correct 125 ms 46860 KB Output is correct
3 Correct 120 ms 46672 KB Output is correct
4 Correct 124 ms 46672 KB Output is correct
5 Correct 20 ms 20820 KB Output is correct
6 Correct 101 ms 38228 KB Output is correct
7 Correct 119 ms 38736 KB Output is correct
8 Correct 148 ms 39248 KB Output is correct
9 Correct 124 ms 39248 KB Output is correct
10 Correct 120 ms 43580 KB Output is correct
11 Correct 128 ms 43088 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 20 ms 20816 KB Output is correct
2 Correct 125 ms 46860 KB Output is correct
3 Correct 120 ms 46672 KB Output is correct
4 Correct 124 ms 46672 KB Output is correct
5 Correct 20 ms 20820 KB Output is correct
6 Correct 101 ms 38228 KB Output is correct
7 Correct 119 ms 38736 KB Output is correct
8 Correct 148 ms 39248 KB Output is correct
9 Correct 124 ms 39248 KB Output is correct
10 Correct 120 ms 43580 KB Output is correct
11 Correct 128 ms 43088 KB Output is correct
12 Correct 33 ms 20568 KB Output is correct
13 Correct 2135 ms 46416 KB Output is correct
14 Correct 1072 ms 46420 KB Output is correct
15 Execution timed out 3567 ms 46008 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 21 ms 20828 KB Output is correct
2 Correct 25 ms 21388 KB Output is correct
3 Correct 31 ms 21588 KB Output is correct
4 Correct 30 ms 21584 KB Output is correct
5 Correct 23 ms 21596 KB Output is correct
6 Correct 33 ms 21584 KB Output is correct
7 Correct 25 ms 20816 KB Output is correct
8 Correct 116 ms 37832 KB Output is correct
9 Correct 120 ms 37984 KB Output is correct
10 Correct 17 ms 20824 KB Output is correct
11 Correct 120 ms 46676 KB Output is correct
12 Correct 122 ms 46772 KB Output is correct
13 Correct 120 ms 46592 KB Output is correct
14 Correct 20 ms 20824 KB Output is correct
15 Correct 113 ms 38280 KB Output is correct
16 Correct 168 ms 38740 KB Output is correct
17 Correct 121 ms 39252 KB Output is correct
18 Correct 128 ms 39080 KB Output is correct
19 Correct 121 ms 43600 KB Output is correct
20 Correct 127 ms 43084 KB Output is correct
21 Correct 125 ms 38464 KB Output is correct
22 Correct 121 ms 38448 KB Output is correct
23 Correct 111 ms 38736 KB Output is correct
24 Correct 113 ms 38736 KB Output is correct
25 Correct 130 ms 40596 KB Output is correct
26 Correct 115 ms 38272 KB Output is correct
27 Correct 106 ms 38156 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 21 ms 20828 KB Output is correct
2 Correct 25 ms 21388 KB Output is correct
3 Correct 31 ms 21588 KB Output is correct
4 Correct 30 ms 21584 KB Output is correct
5 Correct 23 ms 21596 KB Output is correct
6 Correct 33 ms 21584 KB Output is correct
7 Correct 25 ms 20816 KB Output is correct
8 Correct 116 ms 37832 KB Output is correct
9 Correct 120 ms 37984 KB Output is correct
10 Correct 17 ms 20824 KB Output is correct
11 Correct 120 ms 46676 KB Output is correct
12 Correct 122 ms 46772 KB Output is correct
13 Correct 120 ms 46592 KB Output is correct
14 Correct 20 ms 20824 KB Output is correct
15 Correct 113 ms 38280 KB Output is correct
16 Correct 168 ms 38740 KB Output is correct
17 Correct 121 ms 39252 KB Output is correct
18 Correct 128 ms 39080 KB Output is correct
19 Correct 121 ms 43600 KB Output is correct
20 Correct 127 ms 43084 KB Output is correct
21 Correct 125 ms 38464 KB Output is correct
22 Correct 121 ms 38448 KB Output is correct
23 Correct 111 ms 38736 KB Output is correct
24 Correct 113 ms 38736 KB Output is correct
25 Correct 130 ms 40596 KB Output is correct
26 Correct 115 ms 38272 KB Output is correct
27 Correct 106 ms 38156 KB Output is correct
28 Correct 61 ms 20660 KB Output is correct
29 Incorrect 1341 ms 21072 KB Extra information in the output file
30 Halted 0 ms 0 KB -