oj.uz

Submission #1039791

# Submission time Handle Problem Language Result Execution time Memory
1039791 2024-07-31T09:04:35 Z 12345678 Inside information (BOI21_servers) C++17
52.5 / 100
 3500 ms 43084 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":"no")<<endl;
        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<<endl;
        }
    }
}

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 141 ms 17744 KB Output is correct
2 Correct 143 ms 18076 KB Output is correct
3 Correct 148 ms 18004 KB Output is correct
4 Correct 144 ms 17976 KB Output is correct
5 Correct 149 ms 18516 KB Output is correct
6 Correct 168 ms 18148 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 141 ms 17744 KB Output is correct
2 Correct 143 ms 18076 KB Output is correct
3 Correct 148 ms 18004 KB Output is correct
4 Correct 144 ms 17976 KB Output is correct
5 Correct 149 ms 18516 KB Output is correct
6 Correct 168 ms 18148 KB Output is correct
7 Correct 180 ms 17744 KB Output is correct
8 Incorrect 1688 ms 18040 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 142 ms 17844 KB Output is correct
2 Correct 273 ms 33480 KB Output is correct
3 Correct 258 ms 33404 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 142 ms 17844 KB Output is correct
2 Correct 273 ms 33480 KB Output is correct
3 Correct 258 ms 33404 KB Output is correct
4 Correct 201 ms 17708 KB Output is correct
5 Correct 1256 ms 33480 KB Output is correct
6 Correct 1807 ms 35524 KB Output is correct
7 Correct 3443 ms 35416 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 17748 KB Output is correct
2 Correct 278 ms 40020 KB Output is correct
3 Correct 238 ms 40016 KB Output is correct
4 Correct 262 ms 40016 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 17748 KB Output is correct
2 Correct 278 ms 40020 KB Output is correct
3 Correct 238 ms 40016 KB Output is correct
4 Correct 262 ms 40016 KB Output is correct
5 Correct 146 ms 17744 KB Output is correct
6 Correct 2524 ms 39952 KB Output is correct
7 Correct 1303 ms 43084 KB Output is correct
8 Execution timed out 3552 ms 42352 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 17744 KB Output is correct
2 Correct 227 ms 33360 KB Output is correct
3 Correct 244 ms 33876 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 17744 KB Output is correct
2 Correct 227 ms 33360 KB Output is correct
3 Correct 244 ms 33876 KB Output is correct
4 Correct 182 ms 17828 KB Output is correct
5 Execution timed out 3540 ms 33504 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 144 ms 17980 KB Output is correct
2 Correct 257 ms 40016 KB Output is correct
3 Correct 238 ms 39952 KB Output is correct
4 Correct 257 ms 40020 KB Output is correct
5 Correct 141 ms 17724 KB Output is correct
6 Correct 216 ms 33396 KB Output is correct
7 Correct 259 ms 33880 KB Output is correct
8 Correct 249 ms 34384 KB Output is correct
9 Correct 321 ms 34196 KB Output is correct
10 Correct 266 ms 37968 KB Output is correct
11 Correct 275 ms 37596 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 144 ms 17980 KB Output is correct
2 Correct 257 ms 40016 KB Output is correct
3 Correct 238 ms 39952 KB Output is correct
4 Correct 257 ms 40020 KB Output is correct
5 Correct 141 ms 17724 KB Output is correct
6 Correct 216 ms 33396 KB Output is correct
7 Correct 259 ms 33880 KB Output is correct
8 Correct 249 ms 34384 KB Output is correct
9 Correct 321 ms 34196 KB Output is correct
10 Correct 266 ms 37968 KB Output is correct
11 Correct 275 ms 37596 KB Output is correct
12 Correct 154 ms 17868 KB Output is correct
13 Correct 2621 ms 39912 KB Output is correct
14 Correct 1397 ms 43032 KB Output is correct
15 Execution timed out 3543 ms 42380 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 147 ms 17736 KB Output is correct
2 Correct 186 ms 18004 KB Output is correct
3 Correct 143 ms 18000 KB Output is correct
4 Correct 142 ms 18180 KB Output is correct
5 Correct 140 ms 18256 KB Output is correct
6 Correct 151 ms 18132 KB Output is correct
7 Correct 135 ms 17748 KB Output is correct
8 Correct 288 ms 33480 KB Output is correct
9 Correct 236 ms 33312 KB Output is correct
10 Correct 124 ms 17748 KB Output is correct
11 Correct 274 ms 40136 KB Output is correct
12 Correct 281 ms 40016 KB Output is correct
13 Correct 316 ms 40068 KB Output is correct
14 Correct 132 ms 17744 KB Output is correct
15 Correct 232 ms 33388 KB Output is correct
16 Correct 319 ms 33876 KB Output is correct
17 Correct 265 ms 34308 KB Output is correct
18 Correct 267 ms 34356 KB Output is correct
19 Correct 270 ms 38108 KB Output is correct
20 Correct 285 ms 37460 KB Output is correct
21 Correct 291 ms 33344 KB Output is correct
22 Correct 257 ms 33452 KB Output is correct
23 Correct 257 ms 33852 KB Output is correct
24 Correct 251 ms 33872 KB Output is correct
25 Correct 287 ms 35336 KB Output is correct
26 Correct 233 ms 33360 KB Output is correct
27 Correct 243 ms 33360 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 147 ms 17736 KB Output is correct
2 Correct 186 ms 18004 KB Output is correct
3 Correct 143 ms 18000 KB Output is correct
4 Correct 142 ms 18180 KB Output is correct
5 Correct 140 ms 18256 KB Output is correct
6 Correct 151 ms 18132 KB Output is correct
7 Correct 135 ms 17748 KB Output is correct
8 Correct 288 ms 33480 KB Output is correct
9 Correct 236 ms 33312 KB Output is correct
10 Correct 124 ms 17748 KB Output is correct
11 Correct 274 ms 40136 KB Output is correct
12 Correct 281 ms 40016 KB Output is correct
13 Correct 316 ms 40068 KB Output is correct
14 Correct 132 ms 17744 KB Output is correct
15 Correct 232 ms 33388 KB Output is correct
16 Correct 319 ms 33876 KB Output is correct
17 Correct 265 ms 34308 KB Output is correct
18 Correct 267 ms 34356 KB Output is correct
19 Correct 270 ms 38108 KB Output is correct
20 Correct 285 ms 37460 KB Output is correct
21 Correct 291 ms 33344 KB Output is correct
22 Correct 257 ms 33452 KB Output is correct
23 Correct 257 ms 33852 KB Output is correct
24 Correct 251 ms 33872 KB Output is correct
25 Correct 287 ms 35336 KB Output is correct
26 Correct 233 ms 33360 KB Output is correct
27 Correct 243 ms 33360 KB Output is correct
28 Correct 182 ms 17840 KB Output is correct
29 Incorrect 1714 ms 18020 KB Extra information in the output file
30 Halted 0 ms 0 KB -