Submission #471649

#	Time	Username	Problem	Language	Result	Execution time	Memory
471649		NicolaAbusaad2014	Race (IOI11_race)	C++14	0 / 100	2 ms	460 KiB

race

/**
 * Prof.Nicola
**/
#include <bits/stdc++.h>

using namespace std;
#define endl "\n"
#define mp make_pair
#define F first
#define S second
#define REP(i,l,r) for(long long i=(l);i<(r);i++)
#define PER(i,l,r) for(long long i=(r)-1;i>=(l);i--)
long k,ans=1e9;
vector<long long>len;
vector<pair<pair<long,long>,pair<long,long> > >mn;
struct tree
{
    long long n;
    vector<vector<pair<long,long> > >edges;
    vector<long>depth,sz;
    vector<bool>vis;
    void scan0(long x,long p,long long l)
    {
        len[x]=l;
        depth[x]=depth[p]+1;
        sz[x]=1;
        REP(i,0,edges[x].size()){
            if(edges[x][i].F==p||vis[edges[x][i].F]){
                continue;
            }
            scan0(edges[x][i].F,x,l+edges[x][i].S);
            sz[x]+=sz[edges[x][i].F];
        }
    }
    void scan(long x,long p,long long l,long h)
    {
        if(l>k){
            return;
        }
        if(depth[x]<=mn[l].F.F){
            if(mn[l].F.S==h){
                mn[l].F.F=depth[x];
            }
            else{
                mn[l].S=mn[l].F;
                mn[l].F=mp(depth[x],h);
            }
        }
        else if(depth[x]<mn[l].F.S){
            if(mn[l].F.S!=h){
                mn[l].S=mp(depth[x],h);
            }
        }
        REP(i,0,edges[x].size()){
            if(edges[x][i].F==p||vis[edges[x][i].F]){
                continue;
            }
            scan(edges[x][i].F,x,l+edges[x][i].S,h);
        }
    }
    void scan2(long x,long p,long long l,long h)
    {
        if(l>k){
            return;
        }
        if(h==mn[k-l].F.S&&mn[k-l].S.S!=0){
            ans=min(ans,depth[x]+mn[k-l].S.F);
        }
        else if(h!=mn[k-l].F.S){
            ans=min(ans,depth[l]+mn[k-l].F.F);
        }
        REP(i,0,edges[x].size()){
            if(edges[x][i].F==p||vis[edges[x][i].F]){
                continue;
            }
            scan2(edges[x][i].F,x,l+edges[x][i].S,h);
        }
    }
    void scan3(long x,long p,long long l,long h)
    {
        mn[l]=mp(mp(1e9,0),mp(1e9,0));
        REP(i,0,edges[x].size()){
            if(edges[x][i].F==p||vis[edges[x][i].F]){
                continue;
            }
            scan3(edges[x][i].F,x,l+edges[x][i].S,h);
        }
    }
    long centroid(long x,long p,long z)
    {
        long mx=0,node=x;
        REP(i,0,edges[x].size()){
            if(!vis[edges[x][i].F]&&edges[x][i].F!=p&&sz[edges[x][i].F]>mx){
                mx=sz[edges[x][i].F];
                node=edges[x][i].F;
            }
        }
        if(mx<z){
            return x;
        }
        return centroid(node,x,z);
    }
    void read(long nodes,vector<vector<pair<long,long> > >e)
    {
        n=nodes;
        edges=e;
    }
    void build(long long root=1)
    {
        vis.clear();
        vis.resize(n+1);
        depth.clear();
        depth.resize(n+1);
        depth[0]=0;
        sz.clear();
        sz.resize(n+1);
        scan0(root,0,0);
    }
};
tree t;
void solve(long x)
{
    t.scan0(x,0,0);
    x=t.centroid(x,0,(t.sz[x]+1)/2);
    t.vis[x]=true;
    REP(i,0,t.edges[x].size()){
        if(t.vis[t.edges[x][i].F]){
            continue;
        }
        t.scan0(t.edges[x][i].F,0,t.edges[x][i].S);
        t.scan(t.edges[x][i].F,0,t.edges[x][i].S,t.edges[x][i].F);
    }
    REP(i,0,t.edges[x].size()){
        if(t.vis[t.edges[x][i].F]){
            continue;
        }
        t.scan2(t.edges[x][i].F,0,t.edges[x][i].S,t.edges[x][i].F);
    }
    REP(i,0,t.edges[x].size()){
        if(t.vis[t.edges[x][i].F]){
            continue;
        }
        t.scan3(t.edges[x][i].F,0,t.edges[x][i].S,t.edges[x][i].F);
    }
    REP(i,0,t.edges[x].size()){
        if(t.vis[t.edges[x][i].F]){
            continue;
        }
        solve(t.edges[x][i].F);
    }
}
int best_path(int N, int K, int H[][2], int L[])
{
    mn.resize(K+1);
    mn[0]=mp(mp(0,1),mp(0,2));
    REP(i,1,K){
        mn[i]=mp(mp(1e9,0),mp(1e9,0));
    }
    k=K;
    len.resize(N+1);
    vector<vector<pair<long,long> > >e(N+1);
    REP(i,0,N-1){
        e[H[i][0]+1].push_back(mp(H[i][1]+1,L[i]));
        e[H[i][1]+1].push_back(mp(H[i][0]+1,L[i]));
    }
    t.read(N,e);
    t.build();
    solve(1);
    if(ans>=999999998){
        return -1;
    }
    return ans;
}

Compilation message (stderr)

race.cpp: In member function 'void tree::scan0(long int, long int, long long int)':
race.cpp:11:41: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 | #define REP(i,l,r) for(long long i=(l);i<(r);i++)
      |                                         ^
race.cpp:27:9: note: in expansion of macro 'REP'
   27 |         REP(i,0,edges[x].size()){
      |         ^~~
race.cpp: In member function 'void tree::scan(long int, long int, long long int, long int)':
race.cpp:11:41: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 | #define REP(i,l,r) for(long long i=(l);i<(r);i++)
      |                                         ^
race.cpp:54:9: note: in expansion of macro 'REP'
   54 |         REP(i,0,edges[x].size()){
      |         ^~~
race.cpp: In member function 'void tree::scan2(long int, long int, long long int, long int)':
race.cpp:11:41: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 | #define REP(i,l,r) for(long long i=(l);i<(r);i++)
      |                                         ^
race.cpp:72:9: note: in expansion of macro 'REP'
   72 |         REP(i,0,edges[x].size()){
      |         ^~~
race.cpp: In member function 'void tree::scan3(long int, long int, long long int, long int)':
race.cpp:11:41: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 | #define REP(i,l,r) for(long long i=(l);i<(r);i++)
      |                                         ^
race.cpp:82:9: note: in expansion of macro 'REP'
   82 |         REP(i,0,edges[x].size()){
      |         ^~~
race.cpp: In member function 'long int tree::centroid(long int, long int, long int)':
race.cpp:11:41: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 | #define REP(i,l,r) for(long long i=(l);i<(r);i++)
      |                                         ^
race.cpp:92:9: note: in expansion of macro 'REP'
   92 |         REP(i,0,edges[x].size()){
      |         ^~~
race.cpp: In function 'void solve(long int)':
race.cpp:11:41: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 | #define REP(i,l,r) for(long long i=(l);i<(r);i++)
      |                                         ^
race.cpp:126:5: note: in expansion of macro 'REP'
  126 |     REP(i,0,t.edges[x].size()){
      |     ^~~
race.cpp:11:41: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 | #define REP(i,l,r) for(long long i=(l);i<(r);i++)
      |                                         ^
race.cpp:133:5: note: in expansion of macro 'REP'
  133 |     REP(i,0,t.edges[x].size()){
      |     ^~~
race.cpp:11:41: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 | #define REP(i,l,r) for(long long i=(l);i<(r);i++)
      |                                         ^
race.cpp:139:5: note: in expansion of macro 'REP'
  139 |     REP(i,0,t.edges[x].size()){
      |     ^~~
race.cpp:11:41: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 | #define REP(i,l,r) for(long long i=(l);i<(r);i++)
      |                                         ^
race.cpp:145:5: note: in expansion of macro 'REP'
  145 |     REP(i,0,t.edges[x].size()){
      |     ^~~

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