제출 #963531

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
963531		Amr	경주 (Race) (IOI11_race)	C++17	100 / 100	622 ms	45104 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define sz size()
typedef long long ll;
ll k,ans =1e18;
const int N = 200002;
vector<pair<ll,ll> > v[N];
ll siz[N], freq[N*5],vis[N];
void build(ll x, ll par)
{
    siz[x] = 1;
    for(int i = 0; i < v[x].sz; i++)
    {
        ll nn = v[x][i].F;
        if(nn==par||vis[nn]) continue;
        build(nn,x);
        siz[x]+=siz[nn];
    }
}
ll findcn(ll x, ll par, ll m)
{
    for(int i = 0; i < v[x].sz; i++)
    {
        ll nn = v[x][i].F;
        if(nn==par||vis[nn]) continue;
        if(siz[nn]>m/2) return findcn(nn,x,m);
    }
    return x;
}
void get(ll x, ll par, ll w , ll d)
{
    if(w<=k)
    ans=min(ans,freq[k-w]+d);
    for(int i = 0 ; i < v[x].sz; i++)
    {
        ll nn = v[x][i].F;
        if(nn==par||vis[nn]) continue;
        get(nn,x,w+v[x][i].S,d+1);
    }
}
void upd(ll x, ll par, ll w,ll d ,ll tp)
{
    if(w<=k&&tp==1)
        freq[w] = min(freq[w],d);
    else if(w<=k)
        freq[w] = 1e18;
    for(int i = 0 ; i < v[x].sz; i++)
    {
        ll nn = v[x][i].F;
        if(nn==par||vis[nn]) continue;
        upd(nn,x,w+v[x][i].S,d+1,tp);
    }
}
void dfs(ll x)
{
    build(x,-1);
    ll cent = findcn(x, -1, siz[x]/2);
    //cout << cent << endl;
    vis[cent] = 1;
    for(int i = 0; i < v[cent].sz; i++)
    {
        if(vis[v[cent][i].F]) continue;
        get(v[cent][i].F,-1,v[cent][i].S,1);
        upd(v[cent][i].F,-1,v[cent][i].S,1,1);
        //for(int i = 0; i <= k; i++) cout << freq[i] << " "; cout << ans; cout << endl;
    }
    ans = min(ans,freq[k]);
    for(int i = 0; i < v[cent].sz; i++)
    {
        if(vis[v[cent][i].F]) continue;
        upd(v[cent][i].F,-1,v[cent][i].S,1,1-1);
    }
    for(int i = 0; i < v[cent].sz; i++)
        if(!vis[v[cent][i].F]) dfs(v[cent][i].F);
}
int best_path(int N, int K, int H[][2], int L[])
{
    // make the graph
    // dfs(ll x) : build , findcn , make it vis , go from childls and make get upd , theen upd2
    // build(ll x, ll par), findcn(ll x, ll par)
    // get
    // update
    k = K;
    for(int i = 1; i <= k; i++) freq[i] = 1e18;
    for(int i = 0; i < N-1; i++)
    {
        ll x = H[i][0] , y = H[i][1], z = L[i];
        v[x].push_back({y,z});
        v[y].push_back({x,z});
    }
    dfs(0);
    if(ans>=1e18) return -1;
    return ans;

}

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

race.cpp: In function 'void build(ll, ll)':
race.cpp:15: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]
   15 |     for(int i = 0; i < v[x].sz; i++)
      |                      ^
race.cpp: In function 'll findcn(ll, ll, ll)':
race.cpp:25: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]
   25 |     for(int i = 0; i < v[x].sz; i++)
      |                      ^
race.cpp: In function 'void get(ll, ll, ll, ll)':
race.cpp:37:23: 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]
   37 |     for(int i = 0 ; i < v[x].sz; i++)
      |                       ^
race.cpp: In function 'void upd(ll, ll, ll, ll, ll)':
race.cpp:50:23: 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]
   50 |     for(int i = 0 ; i < v[x].sz; i++)
      |                       ^
race.cpp: In function 'void dfs(ll)':
race.cpp:63: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]
   63 |     for(int i = 0; i < v[cent].sz; i++)
      |                      ^
race.cpp:71: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]
   71 |     for(int i = 0; i < v[cent].sz; i++)
      |                      ^
race.cpp:76: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]
   76 |     for(int i = 0; i < v[cent].sz; i++)
      |                      ^

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