QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#474203#5110. Splitstreamarnold518WA 1ms7700kbC++142.7kb2024-07-12 16:37:302024-07-12 16:37:30

Judging History

你现在查看的是最新测评结果

  • [2024-07-12 16:37:30]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:7700kb
  • [2024-07-12 16:37:30]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;

int M, N, Q, K=1;
struct Data
{
    char c;
    int x, y, z;
};

Data A[MAXN+10];
pii B[MAXN+10];
int C[MAXN+10];
vector<int> adj[MAXN+10];

bool vis[MAXN+10];
vector<int> V;
void dfs(int now)
{
    vis[now]=true;
    for(auto nxt : adj[now])
    {
        if(vis[nxt]) continue;
        dfs(nxt);
    }
    V.push_back(now);
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);

    scanf("%d%d%d", &M, &N, &Q);
    for(int i=1; i<=N; i++)
    {
        scanf(" %c%d%d%d", &A[i].c, &A[i].x, &A[i].y, &A[i].z);
        K=max(K, A[i].x);
        K=max(K, A[i].y);
        K=max(K, A[i].z);

        if(A[i].c=='S')
        {
            B[A[i].x].second=i;
            B[A[i].y].first=i;
            B[A[i].z].first=i;
        }
        else
        {
            B[A[i].x].second=i;
            B[A[i].y].second=i;
            B[A[i].z].first=i;
        }
    }

    for(int i=1; i<=K; i++)
    {
        if(B[i].first && B[i].second)
        {
            adj[B[i].first].push_back(B[i].second);
        }
    }

    dfs(1);
    reverse(V.begin(), V.end());

    C[1]=M;
    for(auto it : V)
    {
        if(A[it].c=='S')
        {
            C[A[it].z]=C[A[it].x]/2;
            C[A[it].y]=(C[A[it].x]+1)/2;
        }
        else
        {
            C[A[it].z]=C[A[it].x]+C[A[it].y];
        }
    }
    // for(int i=1; i<=K; i++) printf("%d : %d\n", i, C[i]); 

    while(Q--)
    {
        int a, v;
        scanf("%d%d", &v, &a);
        while(v!=1)
        {
            // printf("%d %d\n", v, a);
            if(C[v]<a) break;

            int p=B[v].first;
            if(A[p].c=='S')
            {
                if(A[p].y==v) a=a+a-1;
                else a=a+a;
                v=A[p].x;
            }
            else
            {
                if(a<=min(C[A[p].x], C[A[p].y])*2)
                {
                    if(a%2)
                    {
                        a=(a+1)/2;
                        v=A[p].x;
                    }
                    else
                    {
                        a=a/2;
                        v=A[p].y;
                    }
                }
                else if(C[A[p].x]<=C[A[p].y])
                {
                    a=a-C[A[p].x];
                    v=A[p].y;
                }
                else
                {
                    a=a-C[A[p].y];
                    v=A[p].x;
                }
            }
        }
        if(C[v]<a) printf("none\n");
        else printf("%d\n", a);
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 7700kb

input:

5 8 26
M 8 9 13
S 2 4 5
S 1 2 3
M 6 5 8
S 4 9 10
S 10 14 15
S 3 6 7
S 7 11 12
2 3
2 4
3 2
3 3
4 2
4 3
5 1
5 2
6 1
6 2
7 1
7 2
8 2
8 3
9 1
9 2
10 1
10 2
11 1
11 2
12 1
13 3
13 4
14 1
14 2
15 1

output:

none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none

result:

wrong answer 1st lines differ - expected: '5', found: 'none'