oj.uz

답안 #999810

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
999810 2024-06-16T07:13:42 Z Theo830 봉쇄 시간 (IOI23_closing) C++17
0 / 100
 1000 ms 34112 KB 
#include <bits/stdc++.h>
#include "closing.h"
using namespace std;
typedef long long ll;
const ll INF = 1e9+7;
const ll MOD = 998244353;
typedef pair<ll,ll> ii;
#define iii pair<ll,ii>
#define f(i,a,b) for(ll i = a;i < b;i++)
#define pb push_back
#define vll vector<ll>
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
///I hope I will get uprating and don't make mistakes
///I will never stop programming
///sqrt(-1) Love C++
///Please don't hack me
///@TheofanisOrfanou Theo830
///Think different approaches (bs,dp,greedy,graphs,shortest paths,mst)
///Stay Calm
///Look for special cases
///Beware of overflow and array bounds
///Think the problem backwards
///Training
vector<vector<ii> >adj;
priority_queue<ii,vector<ii>,greater<ii> >pq;
int max_score(int n, int x, int y, long long k,vector<int>u, vector<int> v, vector<int> w){
    adj.assign(n+5,vector<ii>());
    f(i,0,n-1){
        adj[u[i]].pb(ii(v[i],w[i]));
        adj[v[i]].pb(ii(u[i],w[i]));
    }
    ll dist[n][3];
    f(i,0,n){
        dist[i][0] = dist[i][1] = 1e18;
    }
    dist[x][0] = 0;
    pq.push(ii(0,x));
    while(!pq.empty()){
        ii f = pq.top();
        pq.pop();
        ll w = f.F,u = f.S;
        if(dist[u][0] < w){
            continue;
        }
        for(auto x:adj[u]){
            if(x.S + dist[u][0] < dist[x.F][0]){
                dist[x.F][0] = x.S + dist[u][0];
                pq.push(ii(dist[x.F][0],x.F));
            }
        }
    }
    dist[y][1] = 0;
    pq.push(ii(0,y));
    while(!pq.empty()){
        ii f = pq.top();
        pq.pop();
        ll w = f.F,u = f.S;
        if(dist[u][1] < w){
            continue;
        }
        for(auto x:adj[u]){
            if(x.S + dist[u][1] < dist[x.F][1]){
                dist[x.F][1] = x.S + dist[u][1];
                pq.push(ii(dist[x.F][1],x.F));
            }
        }
    }
    ll sum = 0;
    f(i,0,n){
        dist[i][2] = max(dist[i][0],dist[i][1]);
    }
    vector<ll>other,q;
    f(i,0,x){
        other.pb(dist[i][0]);
    }
    f(i,y+1,n){
        other.pb(dist[i][1]);
    }
    sort(all(other));
    q.pb(0);
    for(auto x:other){
        q.pb(q.back() + x);
    }
    f(i,x,y+1){
        sum += dist[i][1];
    }
    int ans = 0;
    f(i,x,y+1){
        ll cur = sum;
        f(j,i,y+1){
            cur -= dist[i][1];
            cur += dist[i][2];
            ll num = k - cur;
            if(num >= 0){
                int siz = y - x + 1;
                siz += j - i + 1;
                int pos = upper_bound(all(other),num) - other.begin() - 1;
                siz += pos;
                ans = max(ans,siz);
            }
        }
        sum -= dist[i][1];
        sum += dist[i][0];
    }
    sum = 0;
    f(i,x,y+1){
        sum += dist[i][2];
    }
    int siz = 2 * (y - x + 1);
    ll num = k - sum;
    if(num >= 0){
        ans = max(ans,siz);
        ll d = dist[y][0];
        f(i,0,(ll)(other.size())){
            num -= other[i];
            if(num >= 0){
                ans = max(ans,siz + (int)(i+1) + min((int)(i+1),(int)(num / d)));
            }
        }

    }
    int res = 0;
    vector<ll>kame;
    f(i,0,n){
        kame.pb(min(dist[i][0],dist[i][1]));
    }
    sort(all(kame));
    f(i,0,n){
        if(kame[i] <= k){
            k -= kame[i];
            res++;
        }
    }
    ans = max(ans,res);
    return ans;
}
/*
int main()
{

    int Q;
    assert(1 == scanf("%d", &Q));

    std::vector<int> N(Q), X(Q), Y(Q);
    std::vector<long long> K(Q);
    std::vector<std::vector<int>> U(Q), V(Q), W(Q);

    for (int q = 0; q < Q; q++)
    {
        assert(4 == scanf("%d %d %d %lld", &N[q], &X[q], &Y[q], &K[q]));

        U[q].resize(N[q] - 1);
        V[q].resize(N[q] - 1);
        W[q].resize(N[q] - 1);
        for (int i = 0; i < N[q] - 1; ++i)
        {
            assert(3 == scanf("%d %d %d", &U[q][i], &V[q][i], &W[q][i]));
        }
    }
    fclose(stdin);

    std::vector<int> result(Q);
    for (int q = 0; q < Q; q++)
    {
        result[q] = max_score(N[q], X[q], Y[q], K[q], U[q], V[q], W[q]);
    }

    for (int q = 0; q < Q; q++)
    {
        printf("%d\n", result[q]);
    }
    fclose(stdout);

    return 0;
}
*/
/*
2
7 0 2 10
0 1 2
0 3 3
1 2 4
2 4 2
2 5 5
5 6 3
4 0 3 20
0 1 18
1 2 1
2 3 19

1
4 0 3 20
0 1 18
1 2 1
2 3 19
*/

Subtask #0
0.0 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct

Subtask #1
0.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 352 ms 34112 KB Output is correct
2 Execution timed out 1063 ms 32764 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 348 KB 1st lines differ - on the 1st token, expected: '34', found: '38'
5 Halted 0 ms 0 KB -

Subtask #3
0.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 348 KB 1st lines differ - on the 1st token, expected: '34', found: '38'
5 Halted 0 ms 0 KB -

Subtask #4
0.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 348 KB 1st lines differ - on the 1st token, expected: '34', found: '38'
5 Halted 0 ms 0 KB -

Subtask #5
0.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB 1st lines differ - on the 1st token, expected: '34', found: '38'
6 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB 1st lines differ - on the 1st token, expected: '34', found: '38'
6 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB 1st lines differ - on the 1st token, expected: '34', found: '38'
6 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB 1st lines differ - on the 1st token, expected: '34', found: '38'
6 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB 1st lines differ - on the 1st token, expected: '34', found: '38'
6 Halted 0 ms 0 KB -