QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#352588 | #5110. Splitstream | PorNPtree# | WA | 0ms | 3596kb | C++14 | 1.8kb | 2024-03-13 13:35:13 | 2024-03-13 13:35:14 |
Judging History
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;
}
詳細信息
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'