Submission #157149

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
157149	2019-10-09 17:49:48	GioChkhaidze	Race (IOI11_race)	C++14	100 / 100	959 ms	38776 KiB

race

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
#include "race.h"
#define F first
#define S second
using namespace std;
const int Nm=200005;
const int Mm=1000006;
int n,k,ANS=1e9,Lvl[Nm],F[Mm],F1[Mm];
pair < int , int > val;
vector < pair < int , int > > v[Nm];
int Dfs (int x,int size,int &Center,int p) {
  int tot=1;
  for (int i=0; i<v[x].size(); i++)
    if (Lvl[v[x][i].F]==-1 && v[x][i].F!=p) tot+=Dfs(v[x][i].F,size,Center,x);
  if (Center==-1 && (2*tot>=size || p==-1)) Center=x;
  return tot;
}
void Df(int x,int p,int type) {
  if (val.F==k) ANS=min(ANS,val.S);
  if (val.F>=k) return ;
  if (type==1) F[val.F]=min(F[val.F],val.S),ANS=min(ANS,F[val.F]+F1[k-val.F]);
    else 
  if (type==2) F1[val.F]=min(F1[val.F],F[val.F]),F[val.F]=1e9;
    else F1[val.F]=1e9; 
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

race.cpp: In function 'int Dfs(int, int, int&, int)':
race.cpp:17:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<v[x].size(); i++)
                ~^~~~~~~~~~~~
race.cpp: In function 'void Df(int, int, int)':
race.cpp:32:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<v[x].size(); i++) {
                ~^~~~~~~~~~~~
race.cpp: In function 'void Build(int, int, int)':
race.cpp:46:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<v[Center].size(); i++)
                ~^~~~~~~~~~~~~~~~~
race.cpp:56:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<v[Center].size(); i++)
                ~^~~~~~~~~~~~~~~~~

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