oj.uz

답안 #980231

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
980231 2024-05-12T01:26:31 Z vjudge1 봉쇄 시간 (IOI23_closing) C++17
0 / 100
 48 ms 9944 KB 
// hola soy Dember :D
// 31/03/2024

#include "closing.h"
#include <bits/stdc++.h>

#define ll long long 
#define pll pair<ll,ll>
#define f first
#define s second 
#define Z size()
#define pb push_back
#define bp pop_back
#define fo(x,y,z) for(ll x=y; x<=z; x++)
#define of(x,y,z) for(ll x=y; x>=z; x--)
#define all(n) n.begin(), n.end()
#define arr(x,y,z) x+y, x+y+z

using namespace std;

ll n, x, y, k;
ll ans;
vector<vector<pll>> a(n);
vector<map<ll,ll>> vis(n+1), dis(n+1);

void q1(){
    queue<int> q;
    q.push(x);
    while(!q.empty()){
        auto u = q.front(); q.pop();
        for(auto &e:a[u]){
            ll v=e.f, w=e.s;
            if(dis[x].count(v))continue;
            dis[x][v]=dis[x][u]+w;
            q.push(v);
        }
    }
    return;
}

set<pair<int,pll>> q;
vector<ll> c(n);
vector<map<ll,pair<ll,pll>>> l(n);
vector<map<ll,ll>> in(n);

int max_score(int N, int X, int Y, ll K, vector<int>U, vector<int>V, vector<int>W) {
    n=N;x=X;y=Y;k=K;
    
    fo(i,0,n-2)a[U[i]].pb({V[i],W[i]}), a[V[i]].pb({U[i],W[i]});
    
    dis[x][x]=dis[y][y]=0;
    
    q1();
    
    swap(x,y);
    
    q1();
    
    swap(x,y);
    
    q.insert({0,{x,x}});
    q.insert({0,{y,y}});
    
    l[x][x]={0,{x,x}};
    l[y][y]={0,{y,y}};
    in[x][x]=1;
    in[y][y]=1;
    
    while(!q.empty()) {
        auto it=*q.begin(); q.erase(q.begin());
        if (it.f>k) return ans;
        ll xd=it.f, u=it.s.f, z=it.s.s, dm;
        ans++;
        k-=xd;
        
        dm=dis[z][u];
        c[u]=max(c[u], dm);
        vis[z][u]=1;
        
        in[z][u]=0;
        if(in[x][u]){
            dm=dis[x][u]-c[u];
            q.erase(l[x][u]);
            l[x][u]={max(dm,0ll),{u,x}};
            q.insert(l[x][u]);
        }
        if(in[y][u]){
            dm=dis[y][u]-c[u];
            q.erase(l[y][u]);
            l[y][u]={max(dm,0ll),{u,y}};
            q.insert(l[y][u]);
        }
        
        for(auto &e:a[u]){
            ll ola=e.f;
            if (vis[z][ola]) continue;
            ll ace=dis[z][ola];
            ace=max(ace-c[ola],0ll);
            q.insert({ace,{ola,z}});
            in[z][ola]=1;
            l[z][ola]={ace,{ola,z}};
        }
    }
    return ans;
}

Subtask #0
0.0 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 344 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #1
0.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 48 ms 9944 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 344 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 344 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 344 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 344 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 344 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 344 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 344 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 344 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -