Submission #115105

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
115105	2019-06-05 10:10:38	oolimry	Race (IOI11_race)	C++14	43 / 100	3035 ms	255824 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 <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
static vector<ii> adj[200005];
static bool vis[200005];
static unordered_map<int,int> dp[200005];
int k;
int ans = 102345678;
void dfs(int u){
    vis[u] = true;
    for(int i = 0;i < adj[u].size();i++){
        int v = adj[u][i].first;
        int w = adj[u][i].second;
        if(vis[v]) continue;
        dfs(v);
        vector<ii> updates;
        for(ii x : dp[v]){
            int value = w + x.first;
            if(value <= k){
                if(dp[u].find(k-value) != dp[u].end()){
                    ans = min(ans, dp[u][k-value] + x.second + 1);
                }
                updates.push_back({value,x.second+1});
            }
        }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

race.cpp: In function 'void dfs(int)':
race.cpp:15:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i < adj[u].size();i++){
                   ~~^~~~~~~~~~~~~~~

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