oj.uz

Submission #1039776

# Submission time Handle Problem Language Result Execution time Memory
1039776 2024-07-31T08:51:20 Z 12345678 Inside information (BOI21_servers) C++17
50 / 100
 3500 ms 43452 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;
    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);
    t=0;
    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]];
            //cout<<"debug "<<i<<' '<<lst+1<<' '<<cnt[i]<<'\n';
            for (int j=lst+1; j<=cnt[i]; j++) 
            {
                int f=1;
                b[i]=a[idx[j]];
                //cout<<"here "<<i<<' '<<a[i]<<' '<<b[i]<<'\n';
                if (!query(i)) f=0;
                b[i]=b[idx[j]];
                //cout<<"second "<<i<<' '<<a[i]<<' '<<b[i]<<'\n';
                if (!query(i)) f=0;
                tmp+=f;
            }
            cout<<tmp+1<<'\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 24 ms 18768 KB Output is correct
2 Correct 30 ms 19292 KB Output is correct
3 Correct 36 ms 19536 KB Output is correct
4 Correct 32 ms 19544 KB Output is correct
5 Correct 31 ms 19616 KB Output is correct
6 Correct 41 ms 19536 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 24 ms 18768 KB Output is correct
2 Correct 30 ms 19292 KB Output is correct
3 Correct 36 ms 19536 KB Output is correct
4 Correct 32 ms 19544 KB Output is correct
5 Correct 31 ms 19616 KB Output is correct
6 Correct 41 ms 19536 KB Output is correct
7 Correct 68 ms 18748 KB Output is correct
8 Incorrect 1500 ms 19044 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 18780 KB Output is correct
2 Correct 147 ms 36380 KB Output is correct
3 Correct 141 ms 36232 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 29 ms 18780 KB Output is correct
2 Correct 147 ms 36380 KB Output is correct
3 Correct 141 ms 36232 KB Output is correct
4 Correct 85 ms 18768 KB Output is correct
5 Incorrect 1128 ms 36356 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 18776 KB Output is correct
2 Correct 155 ms 43308 KB Output is correct
3 Correct 143 ms 43392 KB Output is correct
4 Correct 151 ms 43344 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 18776 KB Output is correct
2 Correct 155 ms 43308 KB Output is correct
3 Correct 143 ms 43392 KB Output is correct
4 Correct 151 ms 43344 KB Output is correct
5 Correct 43 ms 18784 KB Output is correct
6 Incorrect 2622 ms 41628 KB Extra information in the output file
7 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 18600 KB Output is correct
2 Correct 143 ms 36052 KB Output is correct
3 Correct 165 ms 37136 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 18600 KB Output is correct
2 Correct 143 ms 36052 KB Output is correct
3 Correct 165 ms 37136 KB Output is correct
4 Correct 69 ms 18768 KB Output is correct
5 Execution timed out 3595 ms 36020 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 20 ms 18772 KB Output is correct
2 Correct 147 ms 43452 KB Output is correct
3 Correct 152 ms 43348 KB Output is correct
4 Correct 172 ms 43348 KB Output is correct
5 Correct 24 ms 18768 KB Output is correct
6 Correct 119 ms 36648 KB Output is correct
7 Correct 174 ms 37264 KB Output is correct
8 Correct 156 ms 37468 KB Output is correct
9 Correct 150 ms 37532 KB Output is correct
10 Correct 161 ms 41556 KB Output is correct
11 Correct 168 ms 40784 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 20 ms 18772 KB Output is correct
2 Correct 147 ms 43452 KB Output is correct
3 Correct 152 ms 43348 KB Output is correct
4 Correct 172 ms 43348 KB Output is correct
5 Correct 24 ms 18768 KB Output is correct
6 Correct 119 ms 36648 KB Output is correct
7 Correct 174 ms 37264 KB Output is correct
8 Correct 156 ms 37468 KB Output is correct
9 Correct 150 ms 37532 KB Output is correct
10 Correct 161 ms 41556 KB Output is correct
11 Correct 168 ms 40784 KB Output is correct
12 Correct 42 ms 18520 KB Output is correct
13 Incorrect 2483 ms 42944 KB Extra information in the output file
14 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 25 ms 18768 KB Output is correct
2 Correct 29 ms 19280 KB Output is correct
3 Correct 37 ms 19536 KB Output is correct
4 Correct 31 ms 19544 KB Output is correct
5 Correct 28 ms 19668 KB Output is correct
6 Correct 39 ms 19348 KB Output is correct
7 Correct 29 ms 18780 KB Output is correct
8 Correct 153 ms 36292 KB Output is correct
9 Correct 139 ms 36348 KB Output is correct
10 Correct 24 ms 18780 KB Output is correct
11 Correct 137 ms 43344 KB Output is correct
12 Correct 152 ms 43304 KB Output is correct
13 Correct 141 ms 43348 KB Output is correct
14 Correct 30 ms 18776 KB Output is correct
15 Correct 119 ms 36736 KB Output is correct
16 Correct 129 ms 37204 KB Output is correct
17 Correct 165 ms 37492 KB Output is correct
18 Correct 140 ms 37456 KB Output is correct
19 Correct 154 ms 41552 KB Output is correct
20 Correct 157 ms 40788 KB Output is correct
21 Correct 130 ms 36860 KB Output is correct
22 Correct 133 ms 36808 KB Output is correct
23 Correct 138 ms 37056 KB Output is correct
24 Correct 150 ms 37200 KB Output is correct
25 Correct 155 ms 38400 KB Output is correct
26 Correct 134 ms 36692 KB Output is correct
27 Correct 132 ms 36652 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 25 ms 18768 KB Output is correct
2 Correct 29 ms 19280 KB Output is correct
3 Correct 37 ms 19536 KB Output is correct
4 Correct 31 ms 19544 KB Output is correct
5 Correct 28 ms 19668 KB Output is correct
6 Correct 39 ms 19348 KB Output is correct
7 Correct 29 ms 18780 KB Output is correct
8 Correct 153 ms 36292 KB Output is correct
9 Correct 139 ms 36348 KB Output is correct
10 Correct 24 ms 18780 KB Output is correct
11 Correct 137 ms 43344 KB Output is correct
12 Correct 152 ms 43304 KB Output is correct
13 Correct 141 ms 43348 KB Output is correct
14 Correct 30 ms 18776 KB Output is correct
15 Correct 119 ms 36736 KB Output is correct
16 Correct 129 ms 37204 KB Output is correct
17 Correct 165 ms 37492 KB Output is correct
18 Correct 140 ms 37456 KB Output is correct
19 Correct 154 ms 41552 KB Output is correct
20 Correct 157 ms 40788 KB Output is correct
21 Correct 130 ms 36860 KB Output is correct
22 Correct 133 ms 36808 KB Output is correct
23 Correct 138 ms 37056 KB Output is correct
24 Correct 150 ms 37200 KB Output is correct
25 Correct 155 ms 38400 KB Output is correct
26 Correct 134 ms 36692 KB Output is correct
27 Correct 132 ms 36652 KB Output is correct
28 Correct 68 ms 18768 KB Output is correct
29 Incorrect 1641 ms 19144 KB Extra information in the output file
30 Halted 0 ms 0 KB -