Submission #649676

#	Time	Username	Problem	Language	Result	Execution time	Memory
649676		milisav	Race (IOI11_race)	C++14	100 / 100	388 ms	87536 KiB

race

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

int n,k;
vector<pair<int,int> > a[maxn]; //u a[u] su grane susedne sa u
set<pair<int,int> > s[maxn];
int o1[maxn];
int o2[maxn];
int pok[maxn];
int sol;

void dfs(int u,int pr) {
    pok[u] = u;
    s[u].insert({0,0});
    o1[u] = 0;
    o2[u] = 0;
    int ch = 0;
    for(auto edge:a[u]) {
        int v=edge.first;
        int w=edge.second;
        if(v!=pr) {
            ch++;
            dfs(v,u);
            if(s[pok[u]].size()<=s[pok[v]].size()) pok[u]=pok[v];
        }
    }
    if(ch==0) {
        return;
    }
    for(auto edge:a[u]) {
        int v=edge.first;
        int l=edge.second;
        if(v!=pr) {
            if(pok[u]==pok[v]) {
                o1[pok[u]]+=l;
                o2[pok[u]]+=1;
            }
        }
    }
    s[pok[u]].insert({-o1[pok[u]],-o2[pok[u]]});
    set<pair<int,int> >::iterator it = s[pok[u]].lower_bound({k-o1[pok[u]],-1e9});
    if(it!=s[pok[u]].end() && (*it).first==k-o1[pok[u]]) sol=min(sol,(*it).second+o2[pok[u]]);
    for(auto edge:a[u]) {
        int v=edge.first;
        int l=edge.second;
        if(v!=pr && pok[v]!=pok[u]) {
            for(auto val:s[pok[v]]) {
                int d = val.first + o1[pok[v]];
                int i = val.second + o2[pok[v]];
                set<pair<int,int> >::iterator it = s[pok[u]].lower_bound({k-d-l-o1[pok[u]],-1e9});
                if(it!=s[pok[u]].end() && (*it).first==k-d-l-o1[pok[u]]) sol=min(sol,(*it).second+o2[pok[u]]+i+1);
            }

            for(auto val:s[pok[v]]) {
                int d = val.first + o1[pok[v]];
                int i = val.second + o2[pok[v]];
                s[pok[u]].insert({d+l-o1[pok[u]],i+1-o2[pok[u]]});
                //set<pair<int,int> >::iterator it = s[pok[u]].lower_bound({k-d-l-o1[pok[u]],-1e9});
                //if(it!=s[pok[u]].end() && (*it).first==k-d-l-o1[pok[u]]) sol=min(sol,(*it).second+o2[pok[u]]+i+1);
            }
        }
    }
}

int best_path(int N, int K, int H[][2], int L[]) {
    n=N;
    k=K;
    for(int i=0;i<n-1;i++) {
        a[H[i][0]].push_back({H[i][1],L[i]});
        a[H[i][1]].push_back({H[i][0],L[i]});
    }
    sol=1e9;
    dfs(0,-1);
    if(sol==1e9) return -1;
    else return sol;
}

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

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

int main()
{
  int ans;
  read_input();
  ans = best_path(N,K,H,L);
  printf("%d",ans);

  return 0;
}*/

Compilation message (stderr)

race.cpp: In function 'void dfs(int, int)':
race.cpp:23:13: warning: unused variable 'w' [-Wunused-variable]
   23 |         int w=edge.second;
      |             ^

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