oj.uz

답안 #978020

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
978020 2024-05-08T16:39:16 Z simona1230 경주 (Race) (IOI11_race) C++17
0 / 100
 176 ms 262144 KB 
#include <bits/stdc++.h>
#include "race.h"
using namespace std;

int n,k;
vector<int> v[200001];
vector<int> w[200001];
map<int,int> mp[200001];
int sz[200001];
int used[200001];
int ans=n;

void dfs(int i,int p)
{
    for(int j=0;j<v[i].size();j++)
    {
        int nb=v[i][j],wg=w[i][j];
        if(nb==p||used[nb])continue;

        dfs(nb,i);
        for(auto it=mp[nb].begin();it!=mp[nb].end();it++)
        {
            int vl=it->first+wg;
            int cnt=it->second+1;
            if(mp[i][k-vl])
                ans=min(ans,mp[i][k-vl]+cnt);
        }

        for(auto it=mp[nb].begin();it!=mp[nb].end();it++)
        {
            int vl=it->first+wg;
            int cnt=it->second+1;
            mp[i][vl]=min(mp[i][vl],cnt);
            if(mp[i][vl]==0)mp[i][vl]=cnt;
        }
    }
}


void calc(int i,int p)
{
    sz[i]=1;
    for(int j=0;j<v[i].size();j++)
    {
        int nb=v[i][j];
        if(nb==p||used[nb])continue;

        calc(nb,i);
        sz[i]+=sz[nb];
    }
}

int centroid(int i,int p)
{
    for(int j=0;j<v[i].size();j++)
    {
        int nb=v[i][j];
        if(nb==p||used[nb])continue;
        if(sz[nb]>n/2)return centroid(nb,i);
    }
    return i;
}

void solve(int i)
{
    calc(i,n);
    int c=centroid(i,n);

    dfs(c,n);
    used[c]=1;
    for(int j=0;j<v[i].size();j++)
    {
        int nb=v[i][j];
        if(!used[nb])solve(nb);
    }
}

int best_path(int N, int K, int H[][2], int L[])
{
    n=N;
    k=K;
    for(int i=0;i<n-1;i++)
    {
        v[H[i][0]].push_back(H[i][1]);
        v[H[i][1]].push_back(H[i][0]);
        v[H[i][0]].push_back(L[i]);
        v[H[i][1]].push_back(L[i]);
    }

    solve(1);
    if(ans==n)ans=-1;
    return ans;
}

Compilation message

race.cpp: In function 'void dfs(int, int)':
race.cpp:15:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     for(int j=0;j<v[i].size();j++)
      |                 ~^~~~~~~~~~~~
race.cpp: In function 'void calc(int, int)':
race.cpp:43:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for(int j=0;j<v[i].size();j++)
      |                 ~^~~~~~~~~~~~
race.cpp: In function 'int centroid(int, int)':
race.cpp:55:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     for(int j=0;j<v[i].size();j++)
      |                 ~^~~~~~~~~~~~
race.cpp: In function 'void solve(int)':
race.cpp:71:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     for(int j=0;j<v[i].size();j++)
      |                 ~^~~~~~~~~~~~

Subtask #1
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 176 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 176 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 176 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 176 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -