제출 #1006731

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1006731		Amr	봉쇄 시간 (IOI23_closing)	C++17	8 / 100	87 ms	32340 KiB

closing

// start at :10:36
#include "closing.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define sz size()
#define all(x) (x).begin(),(x).end()
typedef long long ll;
typedef long double ld;
ll n , k;
const int M = 2e5+2;
vector<pair<ll,ll> > v[M];
ll dis[M], p[M];
vector<ll> allx, ally;
set<pair<ll,ll> > s;
void dfs(ll x, ll par,ll d)
{
    p[x] = par;
    dis[x] = d;
    for(int i = 0; i < v[x].sz; i++)
    {
         ll newn = v[x][i].F, w = v[x][i].S;
         if(newn!=par) dfs(newn,x,d+w);
    }
}
int max_score(int N, int X, int Y, long long K,
              std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
    n = N , k = K;
    for(int i = 0 ; i <= n; i++) v[i].clear();
    allx.clear(); ally.clear(); s.clear();
    for(int i = 0; i < n-1; i++)
    {
        ll x = U[i], y = V[i];
        v[x].push_back({y,W[i]});
        v[y].push_back({x,W[i]});
    }
    //
    dfs(X,-1,0);
    s.insert({0,X});
    ll sum = 0;
    while(1)
    {
        ll cur = s.begin()->S;
        ll w = s.begin()->F;
        s.erase(s.begin());
        if(sum+w>k) break;
        sum+=w;
        allx.push_back(w);
        for(int i = 0; i < v[cur].sz; i++)
        {
            ll newn = v[cur][i].F;
            if(newn==p[cur]) continue;
            s.insert({dis[newn],newn});
        }
    }
    //
    s.clear();
    dfs(Y,-1,0);
    s.insert({0,Y});
    sum = 0;
    while(1)
    {
        ll cur = s.begin()->S;
        ll w = s.begin()->F;
        s.erase(s.begin());
        if(sum+w>k) break;
        sum+=w;
        ally.push_back(w);
        for(int i = 0; i < v[cur].sz; i++)
        {
            ll newn = v[cur][i].F;
            if(newn==p[cur]) continue;
            s.insert({dis[newn],newn});
        }
    }
 //   for(int i = 0; i < allx.sz; i++) cout << allx[i] << " "; cout << endl;
  //  for(int i = 0; i < allx.sz; i++) cout << ally[i] << " "; cout << endl;
    for(int i = 1; i < allx.sz ;i++) allx[i] +=allx[i-1];
    for(int i = 1; i < ally.sz ;i++) ally[i] +=ally[i-1];

    ll best = 0;
    for(int i = 0; i < allx.sz; i++)
    {
        ll now = allx[i];
        ll dif = k-now;
        ll l = -1, r = ally.sz;
        while(l+1<r)
        {
            ll mid = (l+r)/2;
            if(ally[mid]<=dif) l = mid;
            else r = mid;
        }
        best = max(best,i+1+l+1);
    }


    return best;
}

컴파일 시 표준 에러 (stderr) 메시지

closing.cpp: In function 'void dfs(ll, ll, ll)':
closing.cpp:22:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for(int i = 0; i < v[x].sz; i++)
      |                      ^
closing.cpp: In function 'int max_score(int, int, int, long long int, std::vector<int>, std::vector<int>, std::vector<int>)':
closing.cpp:52:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |         for(int i = 0; i < v[cur].sz; i++)
      |                          ^
closing.cpp:72:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |         for(int i = 0; i < v[cur].sz; i++)
      |                          ^
closing.cpp:81:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |     for(int i = 1; i < allx.sz ;i++) allx[i] +=allx[i-1];
      |                      ^
closing.cpp:82:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |     for(int i = 1; i < ally.sz ;i++) ally[i] +=ally[i-1];
      |                      ^
closing.cpp:85:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |     for(int i = 0; i < allx.sz; i++)
      |                      ^

• Subtask 0: 0 / 0
• Subtask 1: 8 / 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