oj.uz

답안 #914310

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
914310 2024-01-21T15:16:11 Z Ludissey 봉쇄 시간 (IOI23_closing) C++17
0 / 100
 1000 ms 33484 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]={max(dstY[i],dstX[i]), i};

    int res=K;
    int sum=0;
    while(!singl.empty()){
        sort(singl.begin(),singl.end()); //  sort both
        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;
            int a=-1,b=-1;
            if(!doubl.empty()) {
                for (int i = 0; i < doubl.size(); i++)
                {
                    if(doubl[i].second==singl[0].second||doubl[i].second==singl[1].second) { 
                        a=i;
                        swap(a,b);
                    }
                }
            }
            if(b!=-1){
                singl.push_back({max(dstY[doubl[b].second], dstX[doubl[b].second]),doubl[b].second});
                doubl.erase(doubl.begin()+b); 
                if(b<a) a--;
                if(a!=-1){
                    singl.push_back({max(dstY[doubl[a].second], dstX[doubl[a].second]),doubl[a].second});
                    doubl.erase(doubl.begin()+a); 
                }
            }
            cerr<<singl[0].second << " " << singl[1].second << "- used\n";
            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; }
            }
            cerr<<doubl[0].second << "- double used\n";
            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:66:35: 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]
   66 |                 for (int i = 0; i < doubl.size(); i++)
      |                                 ~~^~~~~~~~~~~~~~
closing.cpp:88: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]
   88 |             for (int i = 0; i < singl.size(); i++)
      |                             ~~^~~~~~~~~~~~~~

Subtask #0
0.0 / 0.0

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

Subtask #1
0.0 / 8.0

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

Subtask #2
0.0 / 9.0

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

Subtask #3
0.0 / 12.0

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

Subtask #4
0.0 / 14.0

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

Subtask #5
0.0 / 9.0

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

Subtask #6
0.0 / 11.0

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

Subtask #7
0.0 / 10.0

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

Subtask #8
0.0 / 10.0

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

Subtask #9
0.0 / 17.0

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