제출 #834033

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
834033		Essa2006	경주 (Race) (IOI11_race)	C++14	100 / 100	864 ms	118844 KiB

race

#include<bits/stdc++.h>
#include "race.h"
using namespace std;
#define ll long long
#define endl '\n'
#define FF first
#define SS second
#define all(a) a.begin(), a.end()
#define mod (ll)(1000000007)
#define MAX_N 500000
const int inf=1e9;
int nn;
vector<ll>P, Order, ofst2;
vector<ll>ofst;
vector<vector<ll>>A;
vector<map<ll, ll>>Has;
map<pair<ll, ll>, ll>mp;
void pre(){
    P.clear(), Order.clear(), ofst.clear(), ofst2.clear(), A.clear(), Has.clear(), mp.clear();
    P.resize(nn+1), ofst.resize(nn+1), ofst2.resize(nn+1), A.resize(nn+1), Has.resize(nn+1);
}

void dfs(int u){
    for(int i=0;i<A[u].size();i++){
        int v=A[u][i];
        if(v!=P[u])
            P[v]=u, dfs(v);
    }
    Order.push_back(u);
}
int best_path(int n, int k, int H[][2], int L[]){
    nn=n;
    pre();
    ll ans=inf;
    for(int i=0;i<n-1;i++){
        int u=H[i][0], v=H[i][1];
        A[u].push_back(v);
        A[v].push_back(u);
        mp[{u, v}]=mp[{v, u}]=L[i];
    }
    dfs(0);
    for(int kk=0;kk<n;kk++){
        int u=Order[kk], mx=-1;
        for(int i=0;i<A[u].size();i++){
            int v=A[u][i];
            if(v==P[u])
                continue;
            if(mx==-1 || Has[v].size()>Has[mx].size())
                mx=v;
        }
        if(mx!=-1)
            ofst[u]=ofst[mx]+mp[{u, mx}], ofst2[u]=ofst2[mx]+1, swap(Has[u], Has[mx]);
        for(int i=0;i<A[u].size();i++){
            int v=A[u][i];
            if(v==P[u] || v==mx)
                continue;
            vector<array<ll, 2>>New;
            for(auto it:Has[v]){
                ll len=it.FF+ofst[v]+mp[{u, v}], need=it.SS+ofst2[v]+1;
                if(Has[u].count(k-len-ofst[u]))
                    ans=min(ans, need+Has[u][k-len-ofst[u]]+ofst2[u]);
                New.push_back({len, need});
            }
            for(int i=0;i<New.size();i++){
                int len=New[i][0], need=New[i][1];
                if(!Has[u].count(len-ofst[u]))
                        Has[u][len-ofst[u]]=need-ofst2[u];
                else
                    Has[u][len-ofst[u]]=min(Has[u][len-ofst[u]], need-ofst2[u]);
            }
        }
        Has[u][-ofst[u]]=-ofst2[u];
        if(Has[u].count(k-ofst[u])){
            ans=min(ans, Has[u][k-ofst[u]]+ofst2[u]);
        }
    }
    if(ans==inf)
        ans=-1;
    return ans;
}

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

race.cpp: In function 'void dfs(int)':
race.cpp:24:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for(int i=0;i<A[u].size();i++){
      |                 ~^~~~~~~~~~~~
race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:44:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |         for(int i=0;i<A[u].size();i++){
      |                     ~^~~~~~~~~~~~
race.cpp:53:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |         for(int i=0;i<A[u].size();i++){
      |                     ~^~~~~~~~~~~~
race.cpp:64:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |             for(int i=0;i<New.size();i++){
      |                         ~^~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 22 / 22
• Subtask 4: 57 / 57