QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#773642#9580. 插排串联laonongmin#WA 1ms5696kbC++231021b2024-11-23 09:40:322024-11-23 09:40:33

Judging History

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

  • [2024-11-23 09:40:33]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5696kb
  • [2024-11-23 09:40:32]
  • 提交

answer

#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define N 100005
#define MOD 998244353
using namespace std;
multiset<int> w;
int n,a[N];
int siz[N];
vector<int> e[N];
void dfs(int u)
{
    if(e[u].size()==0) {siz[u]=a[u];}
    else {siz[u]=0; if(u!=0) w.insert(a[u]);}
    for(auto &&v:e[u])
    {
        dfs(v);
        siz[u] += siz[v];
    }
}
void solve()
{
    cin>>n;
    for(int i=1;i<=n;++i)
    {
        int f;
        cin>>f>>a[i];
        e[f].push_back(i);
    }
    dfs(0);
    if(siz[0]>2200) {cout<<"NO\n"; return;}
    for(int i=1;i<=n;++i)
    {
        if(e[i].size() != 0)
        {
            auto it = w.lower_bound(siz[i]);
            if(it == w.end()) {cout<<"NO\n"; return;}
            else w.erase(it);
        }
    }
    cout<<"YES\n";
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T=1;
    // cin>>T;
    while(T--)
    {
        solve();
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3604kb

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: 1ms
memory: 3716kb

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: 1ms
memory: 3600kb

input:

4
0 1000
1 800
1 500
2 300

output:

YES

result:

ok single line: 'YES'

Test #4:

score: 0
Accepted
time: 1ms
memory: 3648kb

input:

3
0 1000000000
0 1000000000
0 147483647

output:

NO

result:

ok single line: 'NO'

Test #5:

score: -100
Wrong Answer
time: 0ms
memory: 5696kb

input:

3
0 1000000000
0 1000000000
0 147483648

output:

YES

result:

wrong answer 1st lines differ - expected: 'NO', found: 'YES'