Submission #833994

#	Time	Username	Problem	Language	Result	Execution time	Memory
833994		Essa2006	Race (IOI11_race)	C++14	0 / 100	0 ms	340 KiB

race

#include<bits/stdc++.h>
#include "race.h"
using namespace std;
#define ll long long
#define endl '\n'
#define FF first
#define SS second
#define all(a) a.begin(), a.end()
#define mod (ll)(1000000007)
#define MAX_N 500000
const int inf=1e9;
int nn;
vector<int>P, Order, ofst2;
vector<ll>ofst;
vector<vector<int>>A;
vector<map<ll, int>>Has;
map<pair<int, int>, int>mp;
void pre(){
    P.clear(), Order.clear(), ofst.clear(), ofst2.clear(), A.clear(), Has.clear(), mp.clear();
    P.resize(nn+1), ofst.resize(nn+1), ofst2.resize(nn+1), A.resize(nn+1), Has.resize(nn+1);
}

void dfs(int u){
    for(int i=0;i<A[u].size();i++){
        int v=A[u][i];
        if(v!=P[u])
            P[v]=u, dfs(v);
    }
    Order.push_back(u);
}
int best_path(int n, int k, int H[][2], int L[]){
    nn=n;
    pre();
    int ans=inf;
    for(int i=0;i<n-1;i++){
        int u=H[i][0], v=H[i][1];
        A[u].push_back(v);
        A[v].push_back(u);
        mp[{u, v}]=mp[{v, u}]=L[i];
    }
    dfs(0);
    for(int kk=0;kk<n;kk++){
        int u=Order[kk], mx=-1;
        for(int i=0;i<A[u].size();i++){
            int v=A[u][i];
            if(v==P[u])
                continue;
            if(mx==-1 || Has[v].size()>Has[mx].size())
                mx=v;
        }
        if(mx!=-1)
            ofst[u]=ofst[mx]+mp[{u, mx}], ofst2[u]=ofst2[mx]+1, swap(Has[u], Has[mx]);
        for(int i=0;i<A[u].size();i++){
            int v=A[u][i];
            if(v==P[u] || v==mx)
                continue;
            for(auto it:Has[v]){
                int len=it.FF+ofst[v]+mp[{u, v}], need=it.SS+ofst2[v]+1;
                if(Has[u].count(k-len-ofst[u]))
                    ans=min(ans, need+Has[u][k-len-ofst[u]]+ofst2[u]);
                if(!Has[u].count(len-ofst[u]))
                    Has[u][len-ofst[u]]=need-ofst2[u];
                else
                    Has[u][len-ofst[u]]=min(Has[u][len-ofst[u]], need-ofst2[u]);
            }
        }
        Has[u][-ofst[u]]=-ofst2[u];
        if(Has[u].count(k-ofst[u])){
            ans=min(ans, Has[u][k-ofst[u]]+ofst2[u]);
        }
    }
    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);
//  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)':
race.cpp:24:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for(int i=0;i<A[u].size();i++){
      |                 ~^~~~~~~~~~~~
race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:44:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |         for(int i=0;i<A[u].size();i++){
      |                     ~^~~~~~~~~~~~
race.cpp:53:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |         for(int i=0;i<A[u].size();i++){
      |                     ~^~~~~~~~~~~~

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