QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#722826 | #9580. 插排串联 | oqmsac | TL | 356ms | 10660kb | C++23 | 1.3kb | 2024-11-07 20:16:55 | 2024-11-07 20:16:55 |
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];
if(a[i]>2200) a[i]=2201;
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: 2ms
memory: 7812kb
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: 0ms
memory: 7736kb
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: 7732kb
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: 7724kb
input:
3 0 1000000000 0 1000000000 0 147483647
output:
NO
result:
ok single line: 'NO'
Test #5:
score: 0
Accepted
time: 0ms
memory: 7744kb
input:
3 0 1000000000 0 1000000000 0 147483648
output:
NO
result:
ok single line: 'NO'
Test #6:
score: 0
Accepted
time: 10ms
memory: 10660kb
input:
64855 0 69748768 0 450926072 1 699448620 3 918617238 4 106189312 1 617660017 5 31691747 2 373080156 0 363984605 0 937885158 10 300431710 8 485372487 1 661592241 1 836709079 13 895424425 1 824052267 9 887752080 15 952380329 0 595041339 14 632034017 18 752444470 4 311747126 2 289503382 11 213029500 23...
output:
NO
result:
ok single line: 'NO'
Test #7:
score: 0
Accepted
time: 356ms
memory: 9976kb
input:
48750 0 3785579 1 2060436 1 1095269 2 3527822 3 2748694 3 452943 5 427867 3 191538 8 2095981 1 3895276 10 3771233 3 3121067 10 416014 9 1443750 1 699351 8 933800 7 361157 16 423718 10 785063 11 2772134 16 3135666 2 1404821 15 417197 12 1560818 4 2709779 13 2489882 24 1070706 23 2364628 22 3451655 8 ...
output:
YES
result:
ok single line: 'YES'
Test #8:
score: -100
Time Limit Exceeded
input:
84633 0 948740 0 641037 1 718701 2 1491463 4 650546 3 186260 0 1582777 2 3382499 7 422546 7 173919 5 22805 4 2525048 3 55722 13 2477450 4 3136570 0 2480252 8 3021218 5 2229161 6 2865608 19 1079977 17 1435746 4 1313091 12 2415924 23 916623 10 1085785 23 183229 21 2851467 7 3273898 2 1704183 21 108474...
output:
YES