oj.uz

답안 #999861

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
999861 2024-06-16T07:43:35 Z Theo830 봉쇄 시간 (IOI23_closing) C++17
35 / 100
 1000 ms 36160 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;
ll par[200005];
void dfs(ll idx,ll p){
    par[idx] = p;
    for(auto x:adj[idx]){
        if(x.F != p){
            dfs(x.F,idx);
        }
    }
}
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;
    }
    dfs(y,-1);
    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]);
    }
    set<ll>nodes;
    vector<ll>path;
    ll r = x;
    while(r != -1){
        path.pb(r);
        nodes.insert(r);
        r = par[r];
    }
    assert(path[0] == x && path.back() == y);
    vector<ll>other,q;
    f(i,0,n){
        if(!nodes.count(i)){
            other.pb(min(dist[i][0],dist[i][1]));
        }
    }
    sort(all(other));
    q.pb(0);
    for(auto x:other){
        q.pb(q.back() + x);
    }
    for(auto x:path){
        sum += dist[x][1];
    }
    int ans = 0;
    f(i,0,(ll)(path.size())){
        ll cur = sum;
        f(j,i,(ll)(path.size())){
            cur -= dist[path[j]][1];
            cur += dist[path[j]][2];
            ll num = k - cur;
            if(num >= 0){
                int siz = path.size();
                siz += j - i + 1;
                int pos = upper_bound(all(q),num) - q.begin() - 1;
                siz += pos;
                ans = max(ans,siz);
            }
        }
        sum -= dist[path[i]][1];
        sum += dist[path[i]][0];
    }
    sum = 0;
    for(auto x:path){
        sum += dist[x][2];
    }
    int siz = 2 * (ll)(path.size());
    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 344 KB Output is correct

Subtask #1
0.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1042 ms 36160 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 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 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 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 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 600 KB Output is correct
21 Correct 1 ms 344 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 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 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 600 KB Output is correct
21 Correct 1 ms 344 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 1 ms 860 KB Output is correct
27 Correct 1 ms 860 KB Output is correct
28 Correct 13 ms 1076 KB Output is correct
29 Correct 18 ms 860 KB Output is correct
30 Correct 1 ms 860 KB Output is correct
31 Correct 7 ms 1064 KB Output is correct
32 Correct 6 ms 1116 KB Output is correct

Subtask #5
0.0 / 9.0

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

Subtask #6
0.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Incorrect 0 ms 348 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
20 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 600 KB Output is correct
22 Correct 1 ms 344 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Incorrect 0 ms 348 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
27 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 600 KB Output is correct
22 Correct 1 ms 344 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 1 ms 860 KB Output is correct
28 Correct 1 ms 860 KB Output is correct
29 Correct 13 ms 1076 KB Output is correct
30 Correct 18 ms 860 KB Output is correct
31 Correct 1 ms 860 KB Output is correct
32 Correct 7 ms 1064 KB Output is correct
33 Correct 6 ms 1116 KB Output is correct
34 Incorrect 0 ms 348 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
35 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 600 KB Output is correct
22 Correct 1 ms 344 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 1 ms 860 KB Output is correct
28 Correct 1 ms 860 KB Output is correct
29 Correct 13 ms 1076 KB Output is correct
30 Correct 18 ms 860 KB Output is correct
31 Correct 1 ms 860 KB Output is correct
32 Correct 7 ms 1064 KB Output is correct
33 Correct 6 ms 1116 KB Output is correct
34 Incorrect 0 ms 348 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
35 Halted 0 ms 0 KB -