Submission #1112653

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1112653	2024-11-14T13:57:17 Z	ntdaccode	Race (IOI11_race)	C++17	Compilation error	0 ms	0 KB

race

#include<bits/stdc++.h>
#define fori(i,a,b) for(int i=a;i<=b;i++)
#define int long long
#define ii pair<int,int>
#define fi first
#define se second
#define pb push_back
using namespace std;
const int mod=1e9+7;
const int M=1e6+10;
const int N=2e5+10;
int n,k;
vector<ii> ke[N];
bool dd[N];
int sz[N];
int child(int u,int p=0)
{
  sz[u]=1;
  for(auto [v,w]:ke[u]) if(v!=p&&!dd[v]) sz[u]+=child(v,u);
  return sz[u];
}
int centroid(int u,int p=0)
{
  for(auto [v,w]:ke[u]) if(v!=p&&!dd[v]&&sz[v]>n/2) return centroid(v,u);
  return u;
}
int mi[M],kq=1e9;
vector<int> wdel;
void dfs(int u,int tt,int val,int depth,int p=0)
{
  if(val>k) return ;
  if(!tt) {
    kq=min(kq,depth+mi[k-val]);
  }
  else {
    if(mi[val]==1e9) wdel.pb(val);
    mi[val]=min(mi[val],depth);
  }
  for(auto [v,w] :ke[u]) if(v!=p&&!dd[v]) dfs(v,tt,val+w,depth+1,u);
}
void solve(int u)
{
  n=child(u);
  int root=centroid(u);
  dd[root]=true;
  for(auto [v,w] : ke[root]) {
    if(!dd[v]) {
      dfs(v,0,w,1);
      dfs(v,1,w,1);
    }
  }
  for(int v: wdel) mi[v]=1e9;
  wdel.clear();
  for(auto [v,w] :ke[root]){
    if(!dd[v]) solve(v);
  }
}
int32_t main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  #define task "1"
  if(fopen(task".inp","r"))
  {
    freopen(task".inp","r",stdin);
    freopen(task".out","w",stdout);
  }
  cin >> n >> k;
  fori(i,1,n-1)
  {
    int u,v,w;
    cin >> u >> v >> w;
    u++;
    v++;
    ke[u].pb({v,w});
    ke[v].pb({u,w});
  }
  fori(i,1,1e6) mi[i]=1e9;
  mi[0]=0;
  solve(1);
  cout << (kq==1e9 ? -1 : kq) ;
}

Compilation message

race.cpp: In function 'int32_t main()':
race.cpp:66:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |     freopen(task".inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
race.cpp:67:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |     freopen(task".out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccReqYJF.o: in function `main':
race.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cctmYIvG.o:grader.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/cctmYIvG.o: in function `main':
grader.cpp:(.text.startup+0x28): undefined reference to `best_path(int, int, int (*) [2], int*)'
collect2: error: ld returned 1 exit status