Submission #345081

#	Time	Username	Problem	Language	Result	Execution time	Memory
345081		daniel920712	경주 (Race) (IOI11_race)	C++14	21 / 100	3075 ms	15712 KiB

race

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

using namespace std;
long long ans=1000000000;
bool use[200005];
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 KK;
void F(long long fa,long long here,long long dis,long long deg,long long KK)
{
    if(small.find(KK-dis)!=small.end()) ans=min(ans,small[KK-dis]+deg);
    if(dis>KK) return ;
    t.push_back(make_pair(KK,dis));
    for(auto i:Next[here]) if(i.first.first!=fa&&!use[i.first.first]) F(here,i.first.first,dis+i.first.second,deg+1,KK);

}
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&&!use[i.first.first])
        {
            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) center=i;
    small.clear();
    small[0]=0;
    for(auto &i:Next[center])
    {
        if(!use[i.first.first])
        {
            ttt.push_back(i.first.first);
            t.clear();
            F(center,i.first.first,i.first.second,1,KK);
            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);
            }
        }
    }
    use[center]=1;
    for(auto i:ttt) DFS(i);
}
int best_path(int N, int KK, int H[][2], int L[])
{
    ::KK=KK;
    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;
}

Compilation message (stderr)

race.cpp: In function 'void DFS(long long int)':
race.cpp:57:14: warning: 'center' may be used uninitialized in this function [-Wmaybe-uninitialized]
   57 |             F(center,i.first.first,i.first.second,1,KK);
      |             ~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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