Submission #345095

#	Time	Username	Problem	Language	Result	Execution time	Memory
345095		daniel920712	Race (IOI11_race)	C++14	21 / 100	3058 ms	19820 KiB

race

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

using namespace std;
long long ans=1000000000;
bool use[200005];
long long now=2e5;
pair < long long , long long > small[1000005];
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(dis>KK) return ;
    if(small[KK-dis].first==now) ans=min(ans,deg+small[KK-dis].second);
    if(dis==KK) return ;
    t.push_back(make_pair(dis,deg));
    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)
{
    now++;
    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[0]=make_pair(now,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[j.first].first!=now) small[j.first]=make_pair(now,j.second);
                else small[j.first].second=min(small[j.first].second,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:49:15: warning: 'center' may be used uninitialized in this function [-Wmaybe-uninitialized]
   49 |     long long center;
      |               ^~~~~~

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