제출 #345075

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
345075		daniel920712	Race (IOI11_race)	C++14	0 / 100	4 ms	5100 KiB

race

#include "race.h"
#include <vector>
#include <utility>
#include <map>

using namespace std;
long long ans=1000000000;

map < long long , long long > small;
vector < pair < long long , long long > > t;
vector < pair < pair < long long , long long > , long long > > Next[200005];
vector < long long > vis;
long long how[200005];
long long big[200005];
long long tt=0;
long long K;
void F(long long fa,long long here,long long dis,long long deg,long long K)
{
    if(small.find(K-dis)!=small.end()) ans=min(ans,small[K-dis]+deg);
    if(dis>K) return ;
    t.push_back(make_pair(K,dis));
    for(auto i:Next[here]) if(i.first.first!=fa&&i.second) F(here,i.first.first,dis+i.first.second,deg+1,K);

}
void DFS2(long long fa,long long here)
{
    big[here]=0;
    how[here]=1;
    tt++;
    vis.push_back(here);
    for(auto i:Next[here])
    {
        if(i.first.first!=fa&&i.second)
        {
            DFS2(here,i.first.first);
            big[here]=max(big[here],how[i.first.first]);
            how[here]+=how[i.first.first];
        }
    }
}
void DFS(long long here)
{
    vector  < int > ttt;
    vis.clear();
    DFS2(-1,here);
    tt=0;
    long long center;
    for(auto i:vis) if(max(big[i],tt-how[i])<=tt/2+1) center=i;
    vis.clear();
    small.clear();
    small[0]=0;
    for(auto &i:Next[center])
    {
        if(i.second)
        {
            ttt.push_back(i.first.first);
            i.second=0;
            t.clear();
            F(here,i.first.first,i.first.second,1,K);
            for(auto j:t)
            {
                if(small.find(j.first)==small.end()) small[j.first]=j.second;
                else small[j.first]=min(small[j.first],j.second);
            }
        }
    }
    for(auto i:ttt) DFS(i);
}
int best_path(int N, int K, int H[][2], int L[])
{
    ::K=K;
    int i;
    for(i=0;i<N-1;i++)
    {
        Next[H[i][0]].push_back(make_pair(make_pair((long long) H[i][1],(long long) L[i]),1));
        Next[H[i][1]].push_back(make_pair(make_pair((long long) H[i][0],(long long) L[i]),1));
    }
    DFS(0);

    if(ans==1000000000) ans=-1;
    return (int) ans;
}

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

race.cpp: In function 'void DFS(long long int)':
race.cpp:47:15: warning: 'center' may be used uninitialized in this function [-Wmaybe-uninitialized]
   47 |     long long center;
      |               ^~~~~~

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