QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#352588#5110. SplitstreamPorNPtree#WA 0ms3596kbC++141.8kb2024-03-13 13:35:132024-03-13 13:35:14

Judging History

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

  • [2024-03-13 13:35:14]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3596kb
  • [2024-03-13 13:35:13]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=2e4+10;
const long long inf=1e18;
int pre[N],nxt[N];
struct node
{
    int o,x,y,z;
}e[N];
int m,n,q;
long long len[N];
int main()
{
    cin.tie(0)->sync_with_stdio(0);
    cin>>m>>n>>q;
    len[1]=m;
    for(int i=1;i<=n;++i)
    {
        char s[10];
        int x,y,z;
        cin>>s>>x>>y>>z;
        e[i]=node{*s=='S',x,y,z};
        if(*s=='S')
        {
            pre[y]=pre[z]=nxt[x]=i;
            len[y]=len[x]+1>>1,
            len[z]=len[x]>>1;
        }
        else
        {
            pre[z]=nxt[x]=nxt[y]=i;
            len[z]=min(inf,len[x]+len[y]);
        }
    }
    while(q--)
    {
        int x,k;
        cin>>x>>k;
        // cerr<<endl;
        if(len[x]<k){cout<<"none\n";continue;}
        while(x!=1)
        {
            int i=pre[x];
            // cerr<<x<<": "<<k<<" "<<pre[x]<<" : "<<e[i].o<<","<<e[i].x<<","<<e[i].y<<","<<e[i].z<<endl;;
            if(e[i].o==1)//Split
            {
                k=k*2-(e[i].y==x);
                x=e[i].x;
            }
            else//Merge
            {
                long long mn=min(len[e[i].x],len[e[i].y]);
                if(k>mn*2)
                {
                    k-=mn;
                    int mx=len[e[i].x]>len[e[i].y]?e[i].x:e[i].y;
                    x=mx;
                }
                else
                {
                    if(k&1)//from x
                    {
                        k=k+1>>1;
                        x=e[i].x;
                    }
                    else//ffrom y
                    {
                        k>>=1;
                        x=e[i].y;
                    }
                }
            }
        }
        cout<<k<<"\n";
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3596kb

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:

5
none
4
none
none
none
none
none
2
none
4
none
none
none
none
none
none
none
4
none
none
none
none
none
none
none

result:

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