oj.uz

답안 #1077013

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1077013 2024-08-26T20:43:26 Z Lobo 봉쇄 시간 (IOI23_closing) C++17
0 / 100
 1000 ms 36588 KB 
#include "closing.h"
#include<bits/stdc++.h>
using namespace std;
const long long inf = 1e18 + 10;
const int inf1 = 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());
const int maxn = 2e5+10;

vector<int> line;
int wline;
int n, distx[maxn], disty[maxn], isline[maxn];
vector<pair<int,int>> g[maxn];
int makeline(int u, int ant, int final) {
    line.pb(u);
    if(u == final) {
        return 1;
    }

    for(auto V : g[u]) if(V.fr != ant) {
        int v = V.fr;
        int w = V.sc;
        if(makeline(v,u,final) == 1) {
            wline+= w;
            return 1;
        }
    }
    line.pop_back();
    return 0;
}

void makedistx(int u, int ant, int dis) {
    distx[u] = dis;
    for(auto V : g[u]) if(V.fr != ant) {
        int v = V.fr;
        int w = V.sc;
        makedistx(v,u,dis+w);
    }
}

void makedisty(int u, int ant, int dis) {
    disty[u] = dis;
    for(auto V : g[u]) if(V.fr != ant) {
        int v = V.fr;
        int w = V.sc;
        makedisty(v,u,dis+w);
    }
}

int32_t max_score(int32_t N, int32_t X, int32_t Y, long long K,
              std::vector<int32_t> U, std::vector<int32_t> V, std::vector<int32_t> W)
{
    

    line.clear();
    wline = 0;
    n = N;
    for(int i = 0; i < N; i++) {
        isline[i] = distx[i] = disty[i] = 0;
        g[i].clear();
    }
    for(int i = 0; i < U.size(); i++) {
        int u = U[i];
        int v = V[i];
        int w = W[i];
        g[u].pb(mp(v,w));
        g[v].pb(mp(u,w));
    }
    makeline(X,-1,Y);
    // line[0] = X
    // line[line.size()-1] = Y
    for(auto x : line) isline[x] = 1;
    makedistx(X,-1,0);
    makedisty(Y,-1,0);

    int ans = 0;
    {
        // nenhum chega no outro
        for(int rx = 0; rx < line.size(); rx++) {
            for(int ly = line.size()-1; ly >= 0; ly--) {
                priority_queue<pair<int,pair<int,int>>,vector<pair<int,pair<int,int>>>,greater<pair<int,pair<int,int>>>> pq;
                int curk = 0;
                vector<int> atvx(n,0), atvy(n,0);
                for(int i = 0; i <= rx; i++) {
                    atvx[line[i]] = 1;
                }
                for(int i = ly; i < line.size(); i++) {
                    atvy[line[i]] = 1;
                }

                for(int u = 0; u < n; u++) {
                    curk+= max(atvx[u]*distx[u],atvy[u]*disty[u]);
                }

                for(auto V : g[X]) {
                    int v = V.fr;
                    if(isline[v] == 0) {
                        pq.push(mp(distx[v],mp(v,0)));
                    }
                }
                for(auto V : g[Y]) {
                    int v = V.fr;
                    if(isline[v] == 0) {
                        pq.push(mp(disty[v],mp(v,1)));
                    }
                }

                while(pq.size()) {
                    int tp = pq.top().sc.sc;
                    int u = pq.top().sc.fr;
                    pq.pop();
                    if(tp == 0) {
                        if(curk+distx[u] <= K) {
                            atvx[u] = 1;
                            curk+= distx[u];
                            for(auto V : g[u]) {
                                int v = V.fr;
                                if(atvx[v] == 0) {
                                    pq.push(mp(distx[v],mp(v,0)));
                                }
                            }
                        }
                    }
                    else {
                        if(curk+disty[u] <= K) {
                            atvy[u] = 1;
                            curk+= disty[u];
                            for(auto V : g[u]) {
                                int v = V.fr;
                                if(atvy[v] == 0) {
                                    pq.push(mp(disty[v],mp(v,1)));
                                }
                            }
                        }
                    }
                }

                if(curk <= K) {
                    int qtd = 0;
                    for(int i = 0; i < n; i++) {
                        qtd+= atvx[i];
                        qtd+= atvy[i];
                    }

                    ans = max(ans,qtd);
                }


            }
        }

    }

    {
        // os dois chegam um no outro
        vector<int> atv(n,0);
        priority_queue<pair<int,pair<int,int>>,vector<pair<int,pair<int,int>>>,greater<pair<int,pair<int,int>>>> pq;
        int curk = 0;
        for(auto v : line) {
            atv[v] = 2;
            curk+= max(distx[v],disty[v]);
        }

        for(auto V : g[X]) {
            int v = V.fr;
            if(atv[v] == 0) pq.push(mp(distx[v],mp(v,0)));
        }
        for(auto V : g[Y]) {
            int v = V.fr;
            if(atv[v] == 0) pq.push(mp(disty[v],mp(v,1)));
        }
        int qtd = 2;
        while(pq.size()) {
            int tp = pq.top().sc.sc;
            int u = pq.top().sc.fr;
            pq.pop();
            if(tp == 0) {
                if(curk+distx[u] <= K) {
                    atv[u] = 1;
                    curk+= distx[u];
                    for(auto V : g[u]) {
                        int v = V.fr;
                        if(atv[v] == 0) {
                            pq.push(mp(distx[v],mp(v,0)));
                        }
                    }
                }
            }
            else {
                if(curk+disty[u] <= K) {
                    atv[u] = 1;
                    curk+= disty[u];
                    for(auto V : g[u]) {
                        int v = V.fr;
                        if(atv[v] == 0) {
                            pq.push(mp(disty[v],mp(v,1)));
                        }
                    }
                }
            }
            if(curk <= K) {
                ans = max(ans, 2*(int)line.size() + qtd + min(qtd,(K-curk)/wline));
            }
        }
    }

    return (int32_t) ans;
}

Compilation message

closing.cpp: In function 'int32_t max_score(int32_t, int32_t, int32_t, long long int, std::vector<int>, std::vector<int>, std::vector<int>)':
closing.cpp:69:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |     for(int i = 0; i < U.size(); i++) {
      |                    ~~^~~~~~~~~~
closing.cpp:86:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |         for(int rx = 0; rx < line.size(); rx++) {
      |                         ~~~^~~~~~~~~~~~~
closing.cpp:94:35: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |                 for(int i = ly; i < line.size(); i++) {
      |                                 ~~^~~~~~~~~~~~~

Subtask #0
0.0 / 0.0

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

Subtask #1
0.0 / 8.0

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

Subtask #2
0.0 / 9.0

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

Subtask #3
0.0 / 12.0

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

Subtask #4
0.0 / 14.0

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

Subtask #5
0.0 / 9.0

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

Subtask #6
0.0 / 11.0

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

Subtask #7
0.0 / 10.0

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

Subtask #8
0.0 / 10.0

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

Subtask #9
0.0 / 17.0

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