Submission #138354

#	Time	Username	Problem	Language	Result	Execution time	Memory
138354		MrBrionix	Race (IOI11_race)	C++14	100 / 100	728 ms	106356 KiB

race

#include "race.h"
#include <stdio.h>
#include <stdlib.h>
#include<bits/stdc++.h>
using namespace std;
#define MAX_N 500000


vector<int> grafo[200005],peso[200005];
long long k,n,siz[200005],ans;
long long lazy[200005],lazyval[200005];
map<long long,long long> sol[200005];
/*4 3
0 1 1
1 2 2
1 3 4
-----
11 19
0 1 3
0 2 4
2 3 5
3 4 4
4 5 6
0 6 3
6 7 2
6 8 5
8 9 6
8 10 7

*/

void dfs(int nodo,int last){
    
    //cout<<nodo<<" arrivo da "<<last<<endl;
    
    siz[nodo]=1;
    
    int best=0,num;
    long long val=0;
    
    for(int i=0;i<grafo[nodo].size();i++){
        if(grafo[nodo][i]!=last){
            //cout<<"chiamo "<<grafo[nodo][i]<<" "<<nodo<<" "<<last<<endl;
            dfs(grafo[nodo][i],nodo);
            siz[nodo]+=siz[grafo[nodo][i]];
                
            if(siz[grafo[nodo][i]]>best){
                swap(sol[nodo],sol[grafo[nodo][i]]);
                
                lazy[nodo]--;
                lazy[grafo[nodo][i]]++;
                swap(lazy[nodo],lazy[grafo[nodo][i]]);
                
                lazyval[nodo]-=peso[nodo][i];
                lazyval[grafo[nodo][i]]+=peso[nodo][i];
                swap(lazyval[nodo],lazyval[grafo[nodo][i]]);
                
                best=siz[grafo[nodo][i]];
            }
        }
    }
    
    sol[nodo][0-lazyval[nodo]]=0-lazy[nodo];
    
    for(int i=0;i<grafo[nodo].size();i++){
        if(grafo[nodo][i]!=last){
            
            for(auto j : sol[grafo[nodo][i]]){
                num=j.second+lazy[grafo[nodo][i]]+1;
                val=j.first+lazyval[grafo[nodo][i]]+peso[nodo][i];
                
                if(sol[nodo].find(k-val-lazyval[nodo])!=sol[nodo].end())
                ans=min(ans,num+sol[nodo][k-val-lazyval[nodo]]+lazy[nodo]);
            }
            
            for(auto j : sol[grafo[nodo][i]]){
                num=j.second+lazy[grafo[nodo][i]]+1;
                val=j.first+lazyval[grafo[nodo][i]]+peso[nodo][i];
                
                //cout<<"dal figlio "<<grafo[nodo][i]<<" prendo "<<j.second+lazy[grafo[nodo][i]]<<"e "<<j.first+lazyval[grafo[nodo][i]]<<endl;
                
                if(sol[nodo].find(val-lazyval[nodo])!=sol[nodo].end())
                sol[nodo][val-lazyval[nodo]]=min(sol[nodo][val-lazyval[nodo]],num-lazy[nodo]);
                else sol[nodo][val-lazyval[nodo]]=num-lazy[nodo];
            }
        }
    }
    
    if(sol[nodo].find(k-lazyval[nodo])!=sol[nodo].end())ans=min(ans,sol[nodo][k-lazyval[nodo]]+lazy[nodo]);
    
    /*cout<<"info nodo "<<nodo<<":"<<endl;
    
    for(auto i : sol[nodo]){
        cout<<i.first+lazyval[nodo]<<" "<<i.second+lazy[nodo]<<endl;
    }
    
    cout<<"fine -----------"<<endl;*/

}

int best_path(int N, int K, int H[][2], int L[]){
    
    n=N;
    k=K;
    ans=10000000ll;
    for(int i=0;i<n-1;i++){
        grafo[H[i][0]].push_back(H[i][1]);
        grafo[H[i][1]].push_back(H[i][0]);
        peso[H[i][0]].push_back(L[i]);
        peso[H[i][1]].push_back(L[i]);
    }
    
    dfs(0,-1);
    
    if(ans==10000000ll)return -1;
    return ans;
}
/*

static int N, K;
static int H[MAX_N][2];
static int L[MAX_N];
static int solution;

inline 
void my_assert(int e) {if (!e) abort();}

void read_input()
{
  int i;
  my_assert(2==scanf("%d %d",&N,&K));
  for(i=0; i<N-1; i++)
    my_assert(3==scanf("%d %d %d",&H[i][0],&H[i][1],&L[i]));
  //my_assert(1==scanf("%d",&solution));
}


int main()
{
  int ans;
  read_input();
  ans = best_path(N,K,H,L);
  
  cout<<ans<<endl;
  
  if(ans==solution)
    printf("Correct.\n");
  else
    printf("Incorrect. Returned %d, Expected %d.\n",ans,solution);

  return 0;
}*/

Compilation message (stderr)

race.cpp: In function 'void dfs(int, int)':
race.cpp:41:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<grafo[nodo].size();i++){
                 ~^~~~~~~~~~~~~~~~~~~
race.cpp:65:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<grafo[nodo].size();i++){
                 ~^~~~~~~~~~~~~~~~~~~

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