Submission #548611

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
548611	2022-04-14 00:18:15	DavidDamian	Race (IOI11_race)	C++11	100 / 100	486 ms	93388 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 "race.h"
#include <vector>
#include <map>
#include <climits>
#include <iostream>
#ifndef maxn
#define maxn 200005
using namespace std;
typedef long long ll;
struct edge {
  int to;
  ll w;
  edge() {
  }
  edge(int t, int w_) {
    to = t;
    w = w_;
  }
};
vector<edge> adjList[maxn];
int subtreeSize[maxn];
map<ll, int>* sack[maxn]; // Holds pairs (distance to root, min edges to root)
// cannot hold (distance to current node, min edges to current node) since these are relative and would have to be updated
int k; // Searched dist
int minimum; // Answer, minimum number of edges
void update(int u, ll dist, int depth) {
  if ((*sack[u]).find(dist) == (*sack[u]).end())
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

race.cpp: In function 'void search(int, int, int, int, ll)':
race.cpp:48:8: warning: unused variable 'w' [-Wunused-variable]
   48 |     ll w = e.w;
      |        ^

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