oj.uz

답안 #914285

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
914285 2024-01-21T14:16:23 Z Ludissey 봉쇄 시간 (IOI23_closing) C++17
0 / 100
 1000 ms 37068 KB 
#include <bits/stdc++.h>
#include "closing.h"

using namespace std;
#define int long long
#define sz(a){ return (int)a.size(); }

const int INF=1e9;
vector<vector<pair<int,int>>> edges;
vector<int> dstX;
vector<int> dstY;

signed max_score(signed N, signed rootX, signed rootY, long long K, std::vector<signed> U, std::vector<signed> V, std::vector<signed> W){
    vector<pair<int,int>> singl;
    vector<pair<int,int>> doubl;
    edges.clear();
    dstX.clear();
    edges.resize(N);
    dstX.resize(N);
    dstY.resize(N);
    singl.resize(N);
    doubl.resize(N);

    for (int i = 0; i < N-1; i++)
    {
        edges[V[i]].push_back({U[i], W[i]});
        edges[U[i]].push_back({V[i], W[i]});
    }
    vector<bool> visited(N);
    queue<pair<int,int>> queue;
    queue.push({rootX,0});
    while(!queue.empty()){
        int x=queue.front().first,w=queue.front().second; queue.pop();
        if(visited[x]) continue;
        visited[x]=true;
        dstX[x]=w;
        for (auto u: edges[x]) queue.push({u.first, u.second+w});
    }
    visited.clear();
    visited.resize(N);
    queue.push({rootY,0});
    while(!queue.empty()){
        int x=queue.front().first,w=queue.front().second; queue.pop();
        if(visited[x]) continue;
        visited[x]=true;
        dstY[x]=w;
        for (auto u: edges[x]) queue.push({u.first, u.second+w});
    }

    for (int i = 0; i < N; i++) singl[i]={min(dstY[i], dstX[i]),i};
    for (int i = 0; i < N; i++) doubl[i]={dstY[i]+dstX[i], i};

    int res=K;
    int sum=0;
    while(!singl.empty()){
        sort(singl.begin(),singl.end());
        sort(doubl.begin(),doubl.end());
        if(singl.size()==1||(res-(singl[0].first+singl[1].first)<0&&(doubl.empty()||(res-doubl[0].first)<0))){
            if(res-singl[0].first>=0) sum++;
            break; 
        }
        if(doubl.empty() || singl[0].first+singl[1].first<doubl[0].first){
            res-=singl[0].first+singl[1].first;
            if(doubl.empty()) { singl.erase(singl.begin()); singl.erase(singl.begin()); continue; } 
            for (int i = 0; i < doubl.size(); i++)
            {
                if(doubl[i].second==singl[0].second||doubl[i].second==singl[1].second) { 
                    singl.push_back({max(dstY[doubl[i].second], dstX[doubl[i].second]),doubl[i].second});
                    doubl.erase(doubl.begin()+i); 
                }
            }
            singl.erase(singl.begin());
            singl.erase(singl.begin());
        }else{
            res-=doubl[0].first;
            for (int i = 0; i < singl.size(); i++)
            {
                if(singl[i].second==doubl[0].second) { singl.erase(singl.begin()+i); break; }
            }
            doubl.erase(doubl.begin());
        }
        sum+=2;
    }
    
    return (int)sum;
}

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:65:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |             for (int i = 0; i < doubl.size(); i++)
      |                             ~~^~~~~~~~~~~~~~
closing.cpp:76:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |             for (int i = 0; i < singl.size(); i++)
      |                             ~~^~~~~~~~~~~~~~

Subtask #0
0.0 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 348 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 1101 ms 37068 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 9.0

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

Subtask #3
0.0 / 12.0

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

Subtask #4
0.0 / 14.0

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

Subtask #5
0.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 348 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 1 ms 348 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 1 ms 348 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 1 ms 348 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 1 ms 348 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -