oj.uz

답안 #861598

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
861598 2023-10-16T14:33:04 Z faustaadp 봉쇄 시간 (IOI23_closing) C++17
0 / 100
 1000 ms 39640 KB 
#include "closing.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#include <vector>
const ll NN = 2e5 + 5;
vector<pll> v[NN];
ll isi[NN], py[NN], te, ps[NN];
vector<ll> isi2;
void dfs(ll pos, ll par, ll now)
{
    te++;
    isi[te] = pos;
    py[pos] = te;
    ps[te] = now;
    for(auto nx : v[pos])
    {
        if(nx.fi != par)
            dfs(nx.fi, pos, now + nx.se);
    }
}
void dfs2(ll pos, ll par, ll now)
{
    isi2.pb(now);
    for(auto nx : v[pos])
    {
        if(nx.fi != par)
            dfs2(nx.fi, pos, now + nx.se);
    }
}
int max_score(int N, int X, int Y, long long K,
              std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
    te = 0;
    ll R = 0;
    for(ll i = 0; i < N; i++)
    {
        py[i] = 0;
        isi[i + 1] = 0;
        v[i].clear();
    }
    isi2.clear();

    for(ll i = 0; i < V.size(); i++)
    {
        // cout << U[i] << " " << V[i] << "    " << W[i] << "@\n";
        v[U[i]].pb(mp(V[i], W[i]));
        v[V[i]].pb(mp(U[i], W[i]));
    }
    for(ll i = 0; i < N; i++)
        if(v[i].size() == 1)
        {
            R = i;
            break;
        }
    dfs(R, R, 0);
    dfs2(X, X, 0);
    dfs2(Y, Y, 0);
    ll now = K, ret = 0;
    sort(isi2.begin(), isi2.end());
    for(ll i = 0; i < 2 * N; i++)
    {
        if(isi2[i] > now)
            break;
        now -= isi2[i];
        ret++;
    }
    // return ret;
    if(py[X] > py[Y])
        swap(X, Y);
    // cout << py[X] << "  " << py[Y] << " @\n";
    for(ll i = py[X]; i <= py[Y]; i++)
    {
        ll sisa = K, now = 0;
        vector<ll> cal;
        // cout << i << " " << now << " " << sisa << "_\n";
        for(ll j = py[X]; j <= i; j++)
        {
            now++;
            sisa -= ps[j] - ps[py[X]];
        }
        // cout << i << " " << now << " " << sisa << "_\n";
        for(ll j = i + 1; j <= py[Y]; j++)
        {
            now++;
            sisa -= ps[py[Y]] - ps[j];
        }
        // cout << i << " " << now << " " << sisa << "_\n";

        for(ll j = 1; j < py[X]; j++)
        {
            cal.pb(ps[py[X]] - ps[j]); // X
            cal.pb(ps[py[Y]] - ps[py[X]]); // Y
        }

        for(ll j = py[X]; j <= i; j++)
            cal.pb(max(0LL, (ps[py[Y]] - ps[j]) - (ps[j] - ps[py[X]])));

        for(ll j = py[Y] + 1; j <= N; j++)
            cal.pb(ps[j] - ps[py[Y]]);

        if(sisa < 0)
            continue;

        // cout << i << " " << now << " " << sisa << "_\n";
        sort(cal.begin(), cal.end());
        for(ll j = 0; j < cal.size(); j++)
        {
            if(cal[i] > sisa)
                break;
            sisa -= cal[i];
            now++;
        }
        ret = max(ret, now);

    }

    return ret;
}

Compilation message

closing.cpp: In function 'int max_score(int, int, int, long long int, std::vector<int>, std::vector<int>, std::vector<int>)':
closing.cpp:49:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     for(ll i = 0; i < V.size(); i++)
      |                   ~~^~~~~~~~~~
closing.cpp:112:25: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |         for(ll j = 0; j < cal.size(); j++)
      |                       ~~^~~~~~~~~~~~

Subtask #0
0.0 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 9564 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -

Subtask #1
0.0 / 8.0

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

Subtask #2
0.0 / 9.0

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

Subtask #3
0.0 / 12.0

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

Subtask #4
0.0 / 14.0

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

Subtask #5
0.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 9564 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 9564 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 9564 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 9564 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 9564 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -