oj.uz

Submission #840858

# Submission time Handle Problem Language Result Execution time Memory
840858 2023-08-31T19:07:20 Z 79brue Closing Time (IOI23_closing) C++17
43 / 100
 147 ms 37616 KB 
#include "closing.h"
#include <bits/stdc++.h>

typedef long long ll;

using namespace std;

struct dat{
    int x; ll v;
    dat(){}
    dat(int x, ll v): x(x), v(v){}
    bool operator<(const dat &r)const{
        if(v!=r.v) return v<r.v;
        return x<r.x;
    }
};

struct Result{
    int A, B; ll profit;
    Result(){}
    Result(int A, int B, ll profit): A(A), B(B), profit(profit){}

    bool operator<(const Result &r)const{
        return profit < r.profit;
    }
};

int n, s, e; ll k;
vector<pair<int, ll> > link[200002];

ll sdist[200002], edist[200002];
ll v1[200002], v2[200002];

void dfs(int x, int p, ll d, ll *dist){
    dist[x] = d;
    for(pair<int, ll> y: link[x]){
        if(y.first == p) continue;
        dfs(y.first, x, d+y.second, dist);
    }
}

ll arr[200002][3];
ll state[200002];
ll allSum;

set<dat> st[3][3];

void update(int x){
    for(int i=0; i<3; i++){
        if(state[x] == i) continue;
        st[state[x]][i].insert(dat(x, arr[x][i] - arr[x][state[x]]));
    }
}

void remove(int x){
    for(int i=0; i<3; i++){
        if(state[x] == i) continue;
        st[state[x]][i].erase(dat(x, arr[x][i] - arr[x][state[x]]));
    }
}

void up(int x){
    allSum += arr[x][state[x]+1] - arr[x][state[x]];
    state[x]++;
}

void down(int x){
    state[x]--;
    allSum -= arr[x][state[x]+1] - arr[x][state[x]];
}

Result check(int a, int b){
    if(st[a][a+1+(b!=-1)].empty() || (b!=-1 && st[b][b-1].empty())) return Result(0, 0, LLONG_MAX);
    Result ret (0, 0, 0);

    auto it = st[a][a+1+(b!=-1)].begin();
    ret.A = it->x, ret.profit += it->v;

    if(b!=-1){
        it = st[b][b-1].begin();
        ret.B = it->x, ret.profit += it->v;
    }
    return ret;
}

int max_score(int N, int X, int Y, ll K, vector<int> U, vector<int> V, vector<int> W){
    n = N, s = X+1, e = Y+1, k = K;
    for(int i=1; i<=n; i++) link[i].clear();
    for(int i=0; i<n-1; i++){
        link[U[i]+1].push_back(make_pair(V[i]+1, W[i]));
        link[V[i]+1].push_back(make_pair(U[i]+1, W[i]));
    }
    dfs(s, -1, 0, sdist);
    dfs(e, -1, 0, edist);

    int ans = 0;
    {
        vector<ll> v;
        for(int i=1; i<=n; i++) v.push_back(sdist[i]), v.push_back(edist[i]);
        sort(v.begin(), v.end());

        ll sum = 0;
        for(int i=0; i<=n*2; i++){
            sum += v[i];
            if(sum > K) break;
            ans = i+1;
        }
    }

    /// 이제는 따로 처리
    ll se = sdist[e];
    ll base = 0;
    int baseCnt = 0;
    for(int i=1; i<=n; i++){
        if(sdist[i] + edist[i] != se){
            v1[i] = min(sdist[i], edist[i]);
            v2[i] = max(sdist[i], edist[i]) - v1[i];
        }
        else{
            v1[i] = max(sdist[i], edist[i]) - min(sdist[i], edist[i]);
            v2[i] = K+1;
            base += min(sdist[i], edist[i]);
            baseCnt++;
        }
        arr[i][0] = 0;
        arr[i][1] = v1[i];
        arr[i][2] = v1[i] + v2[i];
        state[i] = 0;
//        printf("%d: %lld %lld %lld\n", i, arr[i][0], arr[i][1], arr[i][2]);
    }

    if(base <= K){
        K -= base;
//        printf("base %d %lld\n", baseCnt, base);

        for(int i=0; i<3; i++) for(int j=0; j<3; j++) st[i][j].clear();

        for(int i=1; i<=n; i++){
            update(i);
        }

        int ret = 0;
        allSum = 0;
        for(int turn=1; turn<=2*n; turn++){
            Result tmp (0, 0, LLONG_MAX);
            tmp = min(tmp, check(0, -1));
            tmp = min(tmp, check(1, -1));
            tmp = min(tmp, check(0, 1));
            tmp = min(tmp, check(0, 2));

            remove(tmp.A);
            if(tmp.B) remove(tmp.B);
            up(tmp.A);
            if(tmp.B) down(tmp.B), up(tmp.A);
            update(tmp.A);
            if(tmp.B) update(tmp.B);

            if(K < allSum) break;
            ret++;
        }
        ans = max(ans, ret+baseCnt);
    }
    return ans;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 34932 KB Output is correct
2 Correct 147 ms 37616 KB Output is correct
3 Correct 83 ms 7628 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 2 ms 4984 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 2 ms 4948 KB Output is correct
11 Correct 2 ms 4948 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 2 ms 4984 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 2 ms 4948 KB Output is correct
11 Correct 2 ms 4948 KB Output is correct
12 Correct 2 ms 4948 KB Output is correct
13 Correct 2 ms 4992 KB Output is correct
14 Correct 2 ms 4948 KB Output is correct
15 Correct 2 ms 4948 KB Output is correct
16 Correct 2 ms 4948 KB Output is correct
17 Correct 2 ms 4948 KB Output is correct
18 Correct 2 ms 4948 KB Output is correct
19 Correct 2 ms 5076 KB Output is correct
20 Correct 3 ms 5076 KB Output is correct
21 Correct 3 ms 5076 KB Output is correct
22 Correct 3 ms 5076 KB Output is correct
23 Correct 3 ms 5048 KB Output is correct
24 Correct 2 ms 5076 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 2 ms 4984 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 2 ms 4948 KB Output is correct
11 Correct 2 ms 4948 KB Output is correct
12 Correct 2 ms 4948 KB Output is correct
13 Correct 2 ms 4992 KB Output is correct
14 Correct 2 ms 4948 KB Output is correct
15 Correct 2 ms 4948 KB Output is correct
16 Correct 2 ms 4948 KB Output is correct
17 Correct 2 ms 4948 KB Output is correct
18 Correct 2 ms 4948 KB Output is correct
19 Correct 2 ms 5076 KB Output is correct
20 Correct 3 ms 5076 KB Output is correct
21 Correct 3 ms 5076 KB Output is correct
22 Correct 3 ms 5076 KB Output is correct
23 Correct 3 ms 5048 KB Output is correct
24 Correct 2 ms 5076 KB Output is correct
25 Correct 4 ms 5076 KB Output is correct
26 Correct 5 ms 5844 KB Output is correct
27 Correct 5 ms 5716 KB Output is correct
28 Correct 5 ms 5844 KB Output is correct
29 Correct 5 ms 5840 KB Output is correct
30 Correct 3 ms 5460 KB Output is correct
31 Correct 5 ms 5588 KB Output is correct
32 Correct 3 ms 5588 KB Output is correct

Subtask #5
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 2 ms 4984 KB Output is correct
7 Correct 2 ms 5012 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Correct 2 ms 4948 KB Output is correct
10 Correct 2 ms 4948 KB Output is correct
11 Correct 2 ms 4948 KB Output is correct
12 Correct 2 ms 4948 KB Output is correct
13 Correct 2 ms 4948 KB Output is correct
14 Incorrect 2 ms 4948 KB 1st lines differ - on the 1st token, expected: '38', found: '39'
15 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 2 ms 4984 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Correct 2 ms 4948 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 2 ms 4948 KB Output is correct
12 Correct 2 ms 4948 KB Output is correct
13 Correct 2 ms 4948 KB Output is correct
14 Correct 2 ms 4992 KB Output is correct
15 Correct 2 ms 4948 KB Output is correct
16 Correct 2 ms 4948 KB Output is correct
17 Correct 2 ms 4948 KB Output is correct
18 Correct 2 ms 4948 KB Output is correct
19 Correct 2 ms 5012 KB Output is correct
20 Correct 2 ms 4948 KB Output is correct
21 Correct 2 ms 4948 KB Output is correct
22 Correct 2 ms 4948 KB Output is correct
23 Correct 2 ms 4948 KB Output is correct
24 Correct 2 ms 4948 KB Output is correct
25 Correct 2 ms 4948 KB Output is correct
26 Incorrect 2 ms 4948 KB 1st lines differ - on the 1st token, expected: '38', found: '39'
27 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 2 ms 4984 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Correct 2 ms 4948 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 2 ms 4948 KB Output is correct
12 Correct 2 ms 4948 KB Output is correct
13 Correct 2 ms 4948 KB Output is correct
14 Correct 2 ms 4992 KB Output is correct
15 Correct 2 ms 4948 KB Output is correct
16 Correct 2 ms 4948 KB Output is correct
17 Correct 2 ms 4948 KB Output is correct
18 Correct 2 ms 4948 KB Output is correct
19 Correct 2 ms 4948 KB Output is correct
20 Correct 2 ms 5076 KB Output is correct
21 Correct 3 ms 5076 KB Output is correct
22 Correct 3 ms 5076 KB Output is correct
23 Correct 3 ms 5076 KB Output is correct
24 Correct 3 ms 5048 KB Output is correct
25 Correct 2 ms 5076 KB Output is correct
26 Correct 2 ms 5012 KB Output is correct
27 Correct 2 ms 4948 KB Output is correct
28 Correct 2 ms 4948 KB Output is correct
29 Correct 2 ms 4948 KB Output is correct
30 Correct 2 ms 4948 KB Output is correct
31 Correct 2 ms 4948 KB Output is correct
32 Correct 2 ms 4948 KB Output is correct
33 Incorrect 2 ms 4948 KB 1st lines differ - on the 1st token, expected: '38', found: '39'
34 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 2 ms 4984 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Correct 2 ms 4948 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 2 ms 4948 KB Output is correct
12 Correct 2 ms 4948 KB Output is correct
13 Correct 2 ms 4948 KB Output is correct
14 Correct 2 ms 4992 KB Output is correct
15 Correct 2 ms 4948 KB Output is correct
16 Correct 2 ms 4948 KB Output is correct
17 Correct 2 ms 4948 KB Output is correct
18 Correct 2 ms 4948 KB Output is correct
19 Correct 2 ms 4948 KB Output is correct
20 Correct 2 ms 5076 KB Output is correct
21 Correct 3 ms 5076 KB Output is correct
22 Correct 3 ms 5076 KB Output is correct
23 Correct 3 ms 5076 KB Output is correct
24 Correct 3 ms 5048 KB Output is correct
25 Correct 2 ms 5076 KB Output is correct
26 Correct 4 ms 5076 KB Output is correct
27 Correct 5 ms 5844 KB Output is correct
28 Correct 5 ms 5716 KB Output is correct
29 Correct 5 ms 5844 KB Output is correct
30 Correct 5 ms 5840 KB Output is correct
31 Correct 3 ms 5460 KB Output is correct
32 Correct 5 ms 5588 KB Output is correct
33 Correct 3 ms 5588 KB Output is correct
34 Correct 2 ms 5012 KB Output is correct
35 Correct 2 ms 4948 KB Output is correct
36 Correct 2 ms 4948 KB Output is correct
37 Correct 2 ms 4948 KB Output is correct
38 Correct 2 ms 4948 KB Output is correct
39 Correct 2 ms 4948 KB Output is correct
40 Correct 2 ms 4948 KB Output is correct
41 Incorrect 2 ms 4948 KB 1st lines differ - on the 1st token, expected: '38', found: '39'
42 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 2 ms 4984 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Correct 2 ms 4948 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 2 ms 4948 KB Output is correct
12 Correct 2 ms 4948 KB Output is correct
13 Correct 2 ms 4948 KB Output is correct
14 Correct 2 ms 4992 KB Output is correct
15 Correct 2 ms 4948 KB Output is correct
16 Correct 2 ms 4948 KB Output is correct
17 Correct 2 ms 4948 KB Output is correct
18 Correct 2 ms 4948 KB Output is correct
19 Correct 2 ms 4948 KB Output is correct
20 Correct 2 ms 5076 KB Output is correct
21 Correct 3 ms 5076 KB Output is correct
22 Correct 3 ms 5076 KB Output is correct
23 Correct 3 ms 5076 KB Output is correct
24 Correct 3 ms 5048 KB Output is correct
25 Correct 2 ms 5076 KB Output is correct
26 Correct 4 ms 5076 KB Output is correct
27 Correct 5 ms 5844 KB Output is correct
28 Correct 5 ms 5716 KB Output is correct
29 Correct 5 ms 5844 KB Output is correct
30 Correct 5 ms 5840 KB Output is correct
31 Correct 3 ms 5460 KB Output is correct
32 Correct 5 ms 5588 KB Output is correct
33 Correct 3 ms 5588 KB Output is correct
34 Correct 2 ms 5012 KB Output is correct
35 Correct 2 ms 4948 KB Output is correct
36 Correct 2 ms 4948 KB Output is correct
37 Correct 2 ms 4948 KB Output is correct
38 Correct 2 ms 4948 KB Output is correct
39 Correct 2 ms 4948 KB Output is correct
40 Correct 2 ms 4948 KB Output is correct
41 Incorrect 2 ms 4948 KB 1st lines differ - on the 1st token, expected: '38', found: '39'
42 Halted 0 ms 0 KB -