oj.uz

Submission #1008205

# Submission time Handle Problem Language Result Execution time Memory
1008205 2024-06-26T08:24:36 Z 12345678 Closing Time (IOI23_closing) C++17
0 / 100
 1000 ms 50976 KB 
#include "closing.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=2e5+5;

vector<pair<ll, ll>> g[nx];

struct segtree
{
    struct node
    {
        ll sm, f;
        node(ll sm=0, ll f=0): sm(sm), f(f){}
        friend node operator+(const node &a, const node &b) {return node(a.sm+b.sm, a.f+b.f);}
    } d[4*nx];
    void build(int l, int r, int i)
    {
        d[i]=node(0, 0);
        if (l==r) return;
        int md=(l+r)/2;
        build(l, md, 2*i);
        build(md+1, r, 2*i+1);
    }
    void update(int l, int r, int i, int idx, int f, ll vl)
    {
        if (idx<l||r<idx) return;
        if (l==r) return d[i]=node(d[i].sm+f*vl, d[i].f+f), void();
        int md=(l+r)/2;
        update(l, md, 2*i, idx, f, vl);
        update(md+1, r, 2*i+1, idx, f, vl);
        d[i]=d[2*i]+d[2*i+1];
    }
    ll query(int l, int r, int i, ll vl)
    {
        if (vl>=d[i].sm) return d[i].f;
        if (l==r) return 0;
        int md=(l+r)/2;
        if (d[2*i].sm>vl) return query(l, md, 2*i, vl);
        else return d[2*i].f+query(md+1, r, 2*i+1, vl-d[2*i].sm);
    }
} s;

void dfs(int u, int p, ll cw, vector<ll> &x)
{
    x[u]=cw;
    for (auto [v, w]:g[u]) if (v!=p) dfs(v, u, cw+w, x);
}

int max_score(int N, int X, int Y, long long K,
              std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
    if (X>Y) swap(X, Y);
    for (int i=0; i<N; i++) g[i].clear();
    for (int i=0; i<N-1; i++) g[U[i]].push_back({V[i], W[i]}), g[V[i]].push_back({U[i], W[i]});
    vector<ll> a(N), b(N);
    ll mx=0, t=0;
    map<pair<ll, ll>, ll> mp;
    for (int i=0; i<N; i++) mp[{a[i], 1}]=0, mp[{b[i], 2}]=0;
    for (auto &[x, y]:mp) y=++t;
    dfs(X, X, 0, a);
    dfs(Y, Y, 0, b);
    priority_queue<ll, vector<ll>, greater<ll>> pq;
    for (int i=0; i<N; i++) pq.push(a[i]), pq.push(b[i]);
    ll tmp=K;
    while (!pq.empty()&&pq.top()<=tmp) mx++, tmp-=pq.top(), pq.pop();
    for (int i=0; i<N; i++)
    {
        s.build(1, 2*N, 1);
        ll cur=0, res=0;
        for (int j=0; j<min(i, X); j++) s.update(1, 2*N, 1, mp[{a[j], 1}], 1, a[j]);
        for (int j=max(i, Y)+1; j<N; j++) s.update(1, 2*N, 1, mp[{b[j], 2}], 1, b[j]);
        for (int j=X; j<i; j++) cur+=a[j], res++;
        for (int j=i; j<=Y; j++) cur+=b[j], res++;
        for (int j=i; j<N; j++)
        {
            cur+=max(a[j], b[j]);
            res+=2;
            if (j<=Y) res--, cur-=b[j];
            else s.update(1, 2*N, 1, mp[{b[j], 2}], -1, b[j]);
            if (cur>K) continue;
            mx=max(mx, res+s.query(1, 2*N, 1, K-cur));
        }
    }
    return mx;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 17496 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -

Subtask #1
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1088 ms 50976 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 17500 KB Output is correct
2 Correct 3 ms 17500 KB Output is correct
3 Correct 2 ms 17500 KB Output is correct
4 Correct 2 ms 17500 KB Output is correct
5 Correct 3 ms 17500 KB Output is correct
6 Correct 2 ms 17500 KB Output is correct
7 Correct 2 ms 17496 KB Output is correct
8 Incorrect 3 ms 17500 KB 1st lines differ - on the 1st token, expected: '74', found: '66'
9 Halted 0 ms 0 KB -

Subtask #3
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 17500 KB Output is correct
2 Correct 3 ms 17500 KB Output is correct
3 Correct 2 ms 17500 KB Output is correct
4 Correct 2 ms 17500 KB Output is correct
5 Correct 3 ms 17500 KB Output is correct
6 Correct 2 ms 17500 KB Output is correct
7 Correct 2 ms 17496 KB Output is correct
8 Incorrect 3 ms 17500 KB 1st lines differ - on the 1st token, expected: '74', found: '66'
9 Halted 0 ms 0 KB -

Subtask #4
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 17500 KB Output is correct
2 Correct 3 ms 17500 KB Output is correct
3 Correct 2 ms 17500 KB Output is correct
4 Correct 2 ms 17500 KB Output is correct
5 Correct 3 ms 17500 KB Output is correct
6 Correct 2 ms 17500 KB Output is correct
7 Correct 2 ms 17496 KB Output is correct
8 Incorrect 3 ms 17500 KB 1st lines differ - on the 1st token, expected: '74', found: '66'
9 Halted 0 ms 0 KB -

Subtask #5
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 17496 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 17496 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 17496 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 17496 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 17496 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -