QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#474203 | #5110. Splitstream | arnold518 | WA | 1ms | 7700kb | C++14 | 2.7kb | 2024-07-12 16:37:30 | 2024-07-12 16:37:30 |
Judging History
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'