Submission #151573

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
151573	2019-09-03 15:09:03	AlexPop28	Race (IOI11_race)	C++11	100 / 100	593 ms	87088 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"
using namespace std;
const int INF = (int)1e9;
struct MinMaxMerge {
  map<int, int> dist;
  int lazy_weight, lazy_edges;
  MinMaxMerge() : lazy_weight(0), lazy_edges(0) {
    dist.clear();
  }
};
struct Solver {
  Solver(int k_, const vector<vector<pair<int, int>>> &adj_) :
    n(adj_.size()), k(k_), adj(adj_) {}
  int n, k, ans = INF;
  vector<vector<pair<int, int>>> adj;
  void Merge(MinMaxMerge &curr, MinMaxMerge &him) {
    if (curr.dist.size() < him.dist.size()) {
      swap(curr, him);
    }
    for (auto &p : him.dist) {
      int real_weight = p.first + him.lazy_weight;
      int real_edges = p.second + him.lazy_edges;
      int search = k - real_weight - curr.lazy_weight;
      if (curr.dist.count(search)) {
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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