QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#722815 | #9580. 插排串联 | oqmsac | WA | 2ms | 7744kb | C++23 | 1.3kb | 2024-11-07 20:15:13 | 2024-11-07 20:15:20 |
Judging History
answer
#include<bits/stdc++.h>
#define ll int
#define ull unsigned long long
#define ld long double
#define pii pair<ll,ll>
using namespace std;
#pragma GCC optimize(3)
const ll inf =(1ll<<50);
#define N 1000005
#define M 998244353
#define M1 1000000007
#define M2 1000000009
vector<int> v[N];
int sum[N],fa[N],a[N],flag;
vector<int> st;
void dfs(ll p)
{
if(flag) return;
for(int i=0;i<v[p].size();i++)
{
dfs(v[p][i]);
sum[p]+=sum[v[p][i]];
}
if(!v[p].size())
{
sum[p]=a[p];
}
else if(p!=0)
{
auto it= lower_bound(st.begin(),st.end(),sum[p]);
if(it==st.end())
{
flag=1;
return;
}
// cerr<<sum[p]<<*it<<endl;
st.erase(it);
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>fa[i]>>a[i];
v[fa[i]].push_back(i);
}
for(int i=1;i<=n;i++)
{
if(v[i].size())
{
st.push_back(a[i]);
}
}
sort(st.begin(),st.end());
dfs(0);
if(sum[0]>2200) flag=1;
if(flag) cout<<"NO"<<endl;
else cout<<"YES"<<endl;
return 0;
}
//5
//0 500
//1 700
//1 400
//2 100
//2 300
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 7720kb
input:
5 0 500 1 700 1 400 2 100 2 200
output:
YES
result:
ok single line: 'YES'
Test #2:
score: 0
Accepted
time: 2ms
memory: 7744kb
input:
5 0 500 1 700 1 400 2 100 2 300
output:
NO
result:
ok single line: 'NO'
Test #3:
score: 0
Accepted
time: 2ms
memory: 7648kb
input:
4 0 1000 1 800 1 500 2 300
output:
YES
result:
ok single line: 'YES'
Test #4:
score: 0
Accepted
time: 2ms
memory: 7732kb
input:
3 0 1000000000 0 1000000000 0 147483647
output:
NO
result:
ok single line: 'NO'
Test #5:
score: -100
Wrong Answer
time: 2ms
memory: 7680kb
input:
3 0 1000000000 0 1000000000 0 147483648
output:
YES
result:
wrong answer 1st lines differ - expected: 'NO', found: 'YES'