Submission #980210

#	Time	Username	Problem	Language	Result	Execution time	Memory
980210		vjudge1	Closing Time (IOI23_closing)	C++17	43 / 100	664 ms	20968 KiB

closing

#include <bits/stdc++.h>
#define endl '\n'
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define fo(i,n) for(auto i =0 ; i < n;i++)
#define fore(i,l,r) for(auto i = l; i < r;i++)
#define forex(i,r,l) for(auto i = r; i >= l; i--)
#define ffo(i,n) forex(i,n-1,0)
#define all(x) x.begin(),x.end()
#define lsb(x) x&(-x)
#define sz(x) (int)x.size()
#define gcd(a,b) __gcd(a,b)
#define vii vector<ii>
using namespace std;
using ll = long long; using ull = unsigned long long;
using vi = vector<int>;using ii = pair<int,int>;using mii = map<int,int>;
// #pragma GCC target ("avx2")
// #pragma GCC optimization ("O3")
// #pragma GCC optimization ("unroll-loops")
const int LOG = 13;
struct fenwick{
    vector<ll> ft;int n;
    fenwick(int kkk){n=kkk;ft.resize(n+2,0);}
    void update(int idx, ll val){for(; idx < n; idx += lsb(idx))ft[idx]+=val;}
    ll query(int idx){ll res = 0;for(;idx>0;idx-=lsb(idx))res+=ft[idx];return res;}
    ll query(int l, int r ){if(l>r)return 0;return query(r) - query(l-1);}
    int lwb(ll v){
        ll sum = 0;int pos=0;
        for(int i=LOG; i>=0; i--)
            if(pos + (1 << i) < n and sum + ft[pos + (1 << i)] < v){
                sum += ft[pos + (1 << i)];pos += (1 << i);
            }return pos + 1;
    }
};
int max_score(int n, int x, int y, ll k, vector<int> u, vector<int> v, vector<int> w){
    bool linea= 1;
    fo(i,n-1)if(!(u[i] == i and v[i] == i+1))linea =0;
    if(linea){
        ll suf[n+1]{}, pre[n+1]{};
        fore(i,1,n)pre[i] = (i ? w[i-1] : 0) + (i ? pre[i-1] : 0);
        ffo(i,n-1)suf[i] = w[i] + suf[i+1];
        ll disx[n+1]{};
        for(int i = x-1; i >= 0; i--)disx[i] = disx[i+1] + w[i];
        ll disy[n+1]{} , ans = 0;
        for(int i = y+1; i <= n-1;i++)disy[i] = disy[i-1] + w[i-1];
        int tot = 0;
        vi ord;fo(i,x+1)ord.pb(disx[i]);fore(i,y,n)ord.pb(disy[i]);
        sort(all(ord)) ;
        for(int j = x; j <= n-1; j++ ){
            map<int, int> indices;
            fo(i, sz(ord))indices[ord[i]]=0;
            ans+= pre[j] - pre[x];
            fenwick cnt(2*n+1), sum(2*n+1);
            for(int l=y;l>=0;l--){
                if(l>j)ans+=suf[l]- suf[y];
                else{
                    if(l>x){
                        if(j>=l){
                            if(suf[l]-suf[y] > pre[l] - pre[x]){
                                ans -= pre[l] - pre[x];
                                ans+=suf[l]-suf[y];
                            }
                        }
                        else ans+= suf[l]-suf[y];
                    }
                    else{ans+=suf[l]-suf[y];if(l>=j)ans-=suf[l] - suf[x];}
                }
            }
            for(int i = max(y+1,j+1); i <= n-1; i++){
                int pos = lower_bound(all(ord), disy[i])-ord.begin() ,pos2 = pos;
                pos+=indices[ord[pos]];indices[ord[pos2]]++;
                cnt.update(pos+1, +1);
                sum.update(pos+1, +disy[i]);
            }
            for(int l =0;l<=y;l++){
                if(ans <= k){
                    int rb = sum.lwb(k-ans+1) - 1;
                    rb = cnt.query(1, rb);
                    tot = max(tot, j-x+1 + y-l+1 + rb + max(j-y, 0) + max(x-l, 0));
                }
                if(l>j)ans-=suf[l]- suf[y];
                else{
                    if(l>x){
                        if(j>=l){
                            if(suf[l]-suf[y] > pre[l] - pre[x]){
                                ans += pre[l] - pre[x];
                                ans -=suf[l]-suf[y];
                            }
                        }
                        else ans -= suf[l]-suf[y];
                    }
                    else{ans-=suf[l]-suf[y];if(l>=j)ans+=suf[l] - suf[x];}
                }
                int pos = lower_bound(all(ord), disx[l])-ord.begin(),pos2=pos;
                if(l <= x-1){
                    pos+=indices[ord[pos]];indices[ord[pos2]]++;
                    cnt.update(pos+1, +1);
                    sum.update(pos+1, +disx[l]);
                }
            }
        }
        return tot;
    }
    vector<vector<pair<ll,ll>>>graph(n+2);
    fo(i,n-1){graph[u[i]].pb({v[i], w[i]}), graph[v[i]].pb({u[i], w[i]});}
    // cout << "llegue" << endl ;return 1;
    priority_queue<pair<ll,ll>, vector<pair<ll,ll>>, greater<pair<ll,ll>>> pq;
    pq.push({0, x});pq.push({0,y});
    vi vis(n+1, 0);vis[x]=1; vis[y]=1;
    int ans = 0;ll sumact =0;
    while(sz(pq)){
        auto tp = pq.top();pq.pop();
        // cout << tp.f << " " << tp.s << endl;
        if(tp.f + sumact > k)return ans;
        sumact+=tp.f;
        ans++;
        for(auto [neigh, cost] : graph[tp.s]){
            if(!vis[neigh])pq.push({tp.f + cost, neigh}), vis[neigh] = 1;
        }
    }
    return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 12 / 12
• Subtask 4: 14 / 14
• Subtask 5: 0 / 9
• Subtask 6: 0 / 11
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 17