oj.uz

답안 #1039793

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1039793 2024-07-31T09:09:11 Z 12345678 Inside information (BOI21_servers) C++17
60 / 100
 3500 ms 38740 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()
{
    
    //freopen("server.in","r",stdin);
    //freopen("server.out","w",stdout);
    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

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 17748 KB Output is correct
2 Correct 55 ms 18000 KB Output is correct
3 Correct 62 ms 18008 KB Output is correct
4 Correct 57 ms 18000 KB Output is correct
5 Correct 53 ms 18288 KB Output is correct
6 Correct 65 ms 17988 KB Output is correct

Subtask #2
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 17748 KB Output is correct
2 Correct 55 ms 18000 KB Output is correct
3 Correct 62 ms 18008 KB Output is correct
4 Correct 57 ms 18000 KB Output is correct
5 Correct 53 ms 18288 KB Output is correct
6 Correct 65 ms 17988 KB Output is correct
7 Correct 120 ms 17792 KB Output is correct
8 Incorrect 1659 ms 18028 KB Extra information in the output file
9 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 46 ms 17744 KB Output is correct
2 Correct 277 ms 31936 KB Output is correct
3 Correct 217 ms 31944 KB Output is correct

Subtask #4
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 46 ms 17744 KB Output is correct
2 Correct 277 ms 31936 KB Output is correct
3 Correct 217 ms 31944 KB Output is correct
4 Correct 103 ms 17752 KB Output is correct
5 Correct 1251 ms 33488 KB Output is correct
6 Correct 1822 ms 32216 KB Output is correct
7 Execution timed out 3591 ms 32196 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 17748 KB Output is correct
2 Correct 217 ms 38612 KB Output is correct
3 Correct 244 ms 38504 KB Output is correct
4 Correct 195 ms 38740 KB Output is correct

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 17748 KB Output is correct
2 Correct 217 ms 38612 KB Output is correct
3 Correct 244 ms 38504 KB Output is correct
4 Correct 195 ms 38740 KB Output is correct
5 Correct 61 ms 17752 KB Output is correct
6 Correct 2477 ms 38508 KB Output is correct
7 Correct 1285 ms 38484 KB Output is correct
8 Execution timed out 3553 ms 38480 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 17744 KB Output is correct
2 Correct 170 ms 31880 KB Output is correct
3 Correct 197 ms 32356 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 17744 KB Output is correct
2 Correct 170 ms 31880 KB Output is correct
3 Correct 197 ms 32356 KB Output is correct
4 Correct 89 ms 17748 KB Output is correct
5 Correct 3432 ms 32076 KB Output is correct
6 Correct 1815 ms 35340 KB Output is correct

Subtask #9
12.5 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 17744 KB Output is correct
2 Correct 206 ms 38520 KB Output is correct
3 Correct 207 ms 38488 KB Output is correct
4 Correct 220 ms 38480 KB Output is correct
5 Correct 42 ms 17748 KB Output is correct
6 Correct 184 ms 31828 KB Output is correct
7 Correct 202 ms 32592 KB Output is correct
8 Correct 222 ms 32852 KB Output is correct
9 Correct 207 ms 32772 KB Output is correct
10 Correct 224 ms 36924 KB Output is correct
11 Correct 221 ms 36176 KB Output is correct

Subtask #10
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 17744 KB Output is correct
2 Correct 206 ms 38520 KB Output is correct
3 Correct 207 ms 38488 KB Output is correct
4 Correct 220 ms 38480 KB Output is correct
5 Correct 42 ms 17748 KB Output is correct
6 Correct 184 ms 31828 KB Output is correct
7 Correct 202 ms 32592 KB Output is correct
8 Correct 222 ms 32852 KB Output is correct
9 Correct 207 ms 32772 KB Output is correct
10 Correct 224 ms 36924 KB Output is correct
11 Correct 221 ms 36176 KB Output is correct
12 Correct 68 ms 17848 KB Output is correct
13 Correct 2546 ms 38404 KB Output is correct
14 Correct 1345 ms 38504 KB Output is correct
15 Execution timed out 3571 ms 38260 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 17680 KB Output is correct
2 Correct 59 ms 18004 KB Output is correct
3 Correct 61 ms 18056 KB Output is correct
4 Correct 56 ms 18004 KB Output is correct
5 Correct 51 ms 18128 KB Output is correct
6 Correct 63 ms 18064 KB Output is correct
7 Correct 47 ms 17676 KB Output is correct
8 Correct 202 ms 31928 KB Output is correct
9 Correct 206 ms 31940 KB Output is correct
10 Correct 37 ms 17748 KB Output is correct
11 Correct 211 ms 38616 KB Output is correct
12 Correct 201 ms 38488 KB Output is correct
13 Correct 198 ms 38484 KB Output is correct
14 Correct 49 ms 17848 KB Output is correct
15 Correct 172 ms 32080 KB Output is correct
16 Correct 199 ms 32560 KB Output is correct
17 Correct 222 ms 32868 KB Output is correct
18 Correct 207 ms 32952 KB Output is correct
19 Correct 208 ms 36576 KB Output is correct
20 Correct 253 ms 36048 KB Output is correct
21 Correct 197 ms 33348 KB Output is correct
22 Correct 191 ms 33464 KB Output is correct
23 Correct 200 ms 33872 KB Output is correct
24 Correct 189 ms 32368 KB Output is correct
25 Correct 213 ms 33740 KB Output is correct
26 Correct 200 ms 31712 KB Output is correct
27 Correct 188 ms 31728 KB Output is correct

Subtask #12
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 17680 KB Output is correct
2 Correct 59 ms 18004 KB Output is correct
3 Correct 61 ms 18056 KB Output is correct
4 Correct 56 ms 18004 KB Output is correct
5 Correct 51 ms 18128 KB Output is correct
6 Correct 63 ms 18064 KB Output is correct
7 Correct 47 ms 17676 KB Output is correct
8 Correct 202 ms 31928 KB Output is correct
9 Correct 206 ms 31940 KB Output is correct
10 Correct 37 ms 17748 KB Output is correct
11 Correct 211 ms 38616 KB Output is correct
12 Correct 201 ms 38488 KB Output is correct
13 Correct 198 ms 38484 KB Output is correct
14 Correct 49 ms 17848 KB Output is correct
15 Correct 172 ms 32080 KB Output is correct
16 Correct 199 ms 32560 KB Output is correct
17 Correct 222 ms 32868 KB Output is correct
18 Correct 207 ms 32952 KB Output is correct
19 Correct 208 ms 36576 KB Output is correct
20 Correct 253 ms 36048 KB Output is correct
21 Correct 197 ms 33348 KB Output is correct
22 Correct 191 ms 33464 KB Output is correct
23 Correct 200 ms 33872 KB Output is correct
24 Correct 189 ms 32368 KB Output is correct
25 Correct 213 ms 33740 KB Output is correct
26 Correct 200 ms 31712 KB Output is correct
27 Correct 188 ms 31728 KB Output is correct
28 Correct 89 ms 17748 KB Output is correct
29 Incorrect 1613 ms 17868 KB Extra information in the output file
30 Halted 0 ms 0 KB -