oj.uz

답안 #1039783

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1039783 2024-07-31T08:55:50 Z 12345678 Inside information (BOI21_servers) C++17
2.5 / 100
 3500 ms 39800 KB 
#include <bits/stdc++.h>

using namespace std;

const int nx=250005, kx=18, mod=1;

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]];
            //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<<'\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 24 ms 17796 KB Output is correct
2 Correct 44 ms 18004 KB Output is correct
3 Correct 57 ms 18004 KB Output is correct
4 Correct 45 ms 18264 KB Output is correct
5 Correct 47 ms 18344 KB Output is correct
6 Correct 71 ms 18108 KB Output is correct

Subtask #2
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 17796 KB Output is correct
2 Correct 44 ms 18004 KB Output is correct
3 Correct 57 ms 18004 KB Output is correct
4 Correct 45 ms 18264 KB Output is correct
5 Correct 47 ms 18344 KB Output is correct
6 Correct 71 ms 18108 KB Output is correct
7 Incorrect 24 ms 17756 KB Extra information in the output file
8 Halted 0 ms 0 KB -

Subtask #3
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 17756 KB Output is correct
2 Execution timed out 3517 ms 33208 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 17756 KB Output is correct
2 Execution timed out 3517 ms 33208 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 17756 KB Output is correct
2 Execution timed out 3575 ms 39800 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 17756 KB Output is correct
2 Execution timed out 3575 ms 39800 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 17752 KB Output is correct
2 Execution timed out 3584 ms 33124 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 17752 KB Output is correct
2 Execution timed out 3584 ms 33124 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 17752 KB Output is correct
2 Execution timed out 3540 ms 39756 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 17752 KB Output is correct
2 Execution timed out 3540 ms 39756 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 17752 KB Output is correct
2 Correct 53 ms 18040 KB Output is correct
3 Correct 57 ms 18072 KB Output is correct
4 Correct 47 ms 18012 KB Output is correct
5 Correct 54 ms 18316 KB Output is correct
6 Correct 68 ms 18000 KB Output is correct
7 Correct 31 ms 17752 KB Output is correct
8 Execution timed out 3541 ms 33216 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 17752 KB Output is correct
2 Correct 53 ms 18040 KB Output is correct
3 Correct 57 ms 18072 KB Output is correct
4 Correct 47 ms 18012 KB Output is correct
5 Correct 54 ms 18316 KB Output is correct
6 Correct 68 ms 18000 KB Output is correct
7 Correct 31 ms 17752 KB Output is correct
8 Execution timed out 3541 ms 33216 KB Time limit exceeded
9 Halted 0 ms 0 KB -