제출 #1280102

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1280102		Salazar	Closing Time (IOI23_closing)	C++20	0 / 100	60 ms	23248 KiB

closing

#include <bits/stdc++.h>
using namespace std;
#define int long long

vector<pair<int,int>> G[201000];
int Vis[201000] /*0 - N, 1 - X, 2 - Y, 3 - X e Y*/, Vxy[10] /*1 - X 2 - Y*/, Pes[201000];
priority_queue<pair<int,pair<int,pair<int,int>>>,vector<pair<int,pair<int,pair<int,int>>>>,greater<pair<int,pair<int,pair<int,int>>>>> Q; // valor, atual, pai, base X=1 Y=2

int32_t max_score(int32_t N, int32_t X, int32_t Y, int K, vector<int32_t> U, vector<int32_t> V, vector<int32_t> W) {
    for (int i = 0; i < N-1; i++) {
        G[U[i]].push_back(make_pair(V[i],W[i]));
        G[V[i]].push_back(make_pair(U[i],W[i]));
        Vis[i] = 0;
        Pes[i] = 0;
    }
    Pes[N-1] = 0;
    Vis[N-1] = 0;
    Q.push(make_pair(0, make_pair(X,make_pair(X,1))));
    Q.push(make_pair(0, make_pair(Y,make_pair(Y,2))));
    int S = 0;
    int R = 0;
    while (Q.empty() == false and S<K) {
        pair<int,pair<int,pair<int,int>>> Atual = Q.top();
        Q.pop();
        if (Vis[Atual.second.first]&Atual.second.second.second) continue;
        if (S+Atual.first > K) break;
        if (Atual.second.first == X and Atual.second.second.second==2) Vxy[1] = Atual.first;
        if (Atual.second.first == Y and Atual.second.second.second==1) Vxy[2] = Atual.first;
        S += Atual.first;
        R++;
        Pes[Atual.second.first] = Atual.first;
        int Lp = 0;
        for (int i = 0; i < G[Atual.second.first].size(); i++) {
            if (G[Atual.second.first][i].first == Atual.second.second.first) Lp = G[Atual.second.first][i].second;
            if (Vis[Atual.second.first] == 0) {
                if (Vis[G[Atual.second.first][i].first] == 0) Q.push(make_pair(Atual.first+G[Atual.second.first][i].second,make_pair(G[Atual.second.first][i].first,make_pair(Atual.second.first,Atual.second.second.second))));
                else if (Vis[G[Atual.second.first][i].first]&Atual.second.second.second == 0) {
                    Q.push(make_pair(((Atual.first+G[Atual.second.first][i].second>Pes[G[Atual.second.first][i].first])?Atual.first+G[Atual.second.first][i].second-Pes[G[Atual.second.first][i].first]:0),make_pair(G[Atual.second.first][i].first,make_pair(Atual.second.first,Atual.second.second.second))));
                }
            } else {
                if (Vis[G[Atual.second.first][i].first]&Atual.second.second.second == 0) {
                    Q.push(make_pair(((Atual.first+G[Atual.second.first][i].second>Pes[G[Atual.second.first][i].first])?Atual.first+G[Atual.second.first][i].second-Pes[G[Atual.second.first][i].first]:0),make_pair(G[Atual.second.first][i].first,make_pair(Atual.second.first,Atual.second.second.second))));
                }
            }
        }
        if (Vis[Atual.second.first] == 0 && Vis[Atual.second.second.first] != Atual.second.second.second) Q.push(make_pair((Lp+Pes[Atual.second.second.first]>Atual.first)?Lp+Pes[Atual.second.second.first]-Atual.first:0,make_pair(Atual.second.first,make_pair(Atual.second.second.first,3-Atual.second.second.second))));
        Vis[Atual.second.first] += Atual.second.second.second;
    }
    while (Q.empty()==false) Q.pop();
    for (int i = 0; i < N; i++) while (G[i].empty()==false) G[i].pop_back();
    return R;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 8
• Subtask 2: 0 / 9
• Subtask 3: 0 / 12
• Subtask 4: 0 / 14
• Subtask 5: 0 / 9
• Subtask 6: 0 / 11
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 17