oj.uz

답안 #238619

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
238619 2020-06-12T08:01:08 Z Ruxandra985 경주 (Race) (IOI11_race) C++14
100 / 100
 460 ms 93176 KB 
#include <bits/stdc++.h>
#include "race.h"
#define DIMN 200010
#define MAX_N 500000
using namespace std;
 
vector < pair <int,int> > v[DIMN];
set < pair <long long,int> > per[DIMN];
int sub[DIMN] , f[DIMN] , distanta[DIMN];
long long add[DIMN];
int sol;
 
void precalc (int nod , int tt){
    int i , vecin;
 
    sub[nod] = 1;
    for (i = 0 ; i < v[nod].size() ; i++){
        vecin = v[nod][i].first;
        if (vecin != tt && !f[vecin]){
            precalc (vecin , nod);
            sub[nod] += sub[vecin];
        }
    }
 
}
 
void dfs (int nod , int tt , int k){
    int i , vecin , maxi = 0 , fiu ;
    long long rms;
    set < pair <long long,int> > :: iterator aux;
 
    for (i = 0 ; i < v[nod].size() ; i++){
        vecin = v[nod][i].first;
        if (vecin != tt && sub[vecin] > maxi){
            maxi = sub[vecin];
            fiu = vecin;
        }
    }
 
 
    for (i = 0 ; i < v[nod].size() ; i++){
        vecin = v[nod][i].first;
        if (vecin != tt){
            dfs (vecin , nod , k);
            add[vecin] += v[nod][i].second;
            distanta[vecin]++;
        }
    }
 
 
    if (maxi){
 
        per[nod].swap(per[fiu]);
        add[nod] = add[fiu];
        distanta[nod] = distanta[fiu];
 
        for (i = 0 ; i < v[nod].size() ; i++){
            vecin = v[nod][i].first;
 
            if (vecin != tt){
 
                if (vecin != fiu){
                    rms = k - v[nod][i].second - add[nod];
 
                    aux = per[nod].upper_bound(make_pair(rms , -2000000000));
 
                    if (aux != per[nod].end() && aux->first == rms){
 
                        sol = min(sol , 1 + aux->second + distanta[nod]);
 
                    }
                }
 
 
                per[nod].insert(make_pair(v[nod][i].second - add[nod] , 1 - distanta[nod]));
 
 
            }
 
            if (vecin != tt && vecin != fiu){
 
                /// sa zicem ca nod ar fi lca - ul , un capat pana acum , unul in vecin
 
                for (set <pair <long long,int> > :: iterator it = per[vecin].begin() ; it != per[vecin].end() ; it++){
 
                    if (it->first + add[vecin] > k)
                        continue;
 
                    rms = k - (it->first + add[vecin]) - add[nod];
 
                    aux = per[nod].upper_bound(make_pair(rms , -2000000000));
 
                    if (aux != per[nod].end() && aux->first == rms){
 
                        sol = min(sol , it->second + distanta[vecin] + aux->second + distanta[nod]);
 
                    }
 
                }
 
 
 
                /// vezi cum le unesti
 
                for (set <pair <long long,int> > :: iterator it = per[vecin].begin() ; it != per[vecin].end() ; it++){
 
                    if (it->first + add[vecin] > k)
                        continue; /// nu imi pasa
 
 
                    per[nod].insert(make_pair(it->first + add[vecin] - add[nod] , it->second + distanta[vecin] - distanta[nod]));
 
 
                }
 
 
            }
        }
 
 
    }
 
    aux = per[nod].upper_bound(make_pair(k - add[nod] , -2000000000));
    if (aux != per[nod].end() && aux->first == k - add[nod]){
        sol = min(sol , aux->second + distanta[nod]);
    }
 
}
 
int best_path(int n, int k, int h[][2], int l[]){
    int i;
 
    for (i = 0 ; i < n - 1 ; i++){
 
        h[i][1]++;
        h[i][0]++;
 
        v[h[i][0]].push_back(make_pair(h[i][1] , l[i]));
        v[h[i][1]].push_back(make_pair(h[i][0] , l[i]));
 
    }
 
    precalc (1 , 0);
 
    sol = 2000000000;
 
    dfs (1 , 0 , k);
 
    return (sol == 2000000000 ? -1 : sol);
 
}

Compilation message

race.cpp: In function 'void precalc(int, int)':
race.cpp:17:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0 ; i < v[nod].size() ; i++){
                  ~~^~~~~~~~~~~~~~~
race.cpp: In function 'void dfs(int, int, int)':
race.cpp:32:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0 ; i < v[nod].size() ; i++){
                  ~~^~~~~~~~~~~~~~~
race.cpp:41:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0 ; i < v[nod].size() ; i++){
                  ~~^~~~~~~~~~~~~~~
race.cpp:57:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i = 0 ; i < v[nod].size() ; i++){
                      ~~^~~~~~~~~~~~~~~
race.cpp:28:32: warning: 'fiu' may be used uninitialized in this function [-Wmaybe-uninitialized]
     int i , vecin , maxi = 0 , fiu ;
                                ^~~

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 14464 KB Output is correct
2 Correct 12 ms 14464 KB Output is correct
3 Correct 13 ms 14464 KB Output is correct
4 Correct 13 ms 14464 KB Output is correct
5 Correct 13 ms 14464 KB Output is correct
6 Correct 13 ms 14464 KB Output is correct
7 Correct 13 ms 14464 KB Output is correct
8 Correct 13 ms 14464 KB Output is correct
9 Correct 13 ms 14464 KB Output is correct
10 Correct 13 ms 14464 KB Output is correct
11 Correct 13 ms 14464 KB Output is correct
12 Correct 13 ms 14464 KB Output is correct
13 Correct 13 ms 14464 KB Output is correct
14 Correct 13 ms 14592 KB Output is correct
15 Correct 14 ms 14464 KB Output is correct
16 Correct 12 ms 14464 KB Output is correct
17 Correct 13 ms 14464 KB Output is correct
18 Correct 13 ms 14464 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 14464 KB Output is correct
2 Correct 12 ms 14464 KB Output is correct
3 Correct 13 ms 14464 KB Output is correct
4 Correct 13 ms 14464 KB Output is correct
5 Correct 13 ms 14464 KB Output is correct
6 Correct 13 ms 14464 KB Output is correct
7 Correct 13 ms 14464 KB Output is correct
8 Correct 13 ms 14464 KB Output is correct
9 Correct 13 ms 14464 KB Output is correct
10 Correct 13 ms 14464 KB Output is correct
11 Correct 13 ms 14464 KB Output is correct
12 Correct 13 ms 14464 KB Output is correct
13 Correct 13 ms 14464 KB Output is correct
14 Correct 13 ms 14592 KB Output is correct
15 Correct 14 ms 14464 KB Output is correct
16 Correct 12 ms 14464 KB Output is correct
17 Correct 13 ms 14464 KB Output is correct
18 Correct 13 ms 14464 KB Output is correct
19 Correct 12 ms 14464 KB Output is correct
20 Correct 12 ms 14464 KB Output is correct
21 Correct 13 ms 14592 KB Output is correct
22 Correct 13 ms 14592 KB Output is correct
23 Correct 13 ms 14592 KB Output is correct
24 Correct 14 ms 14592 KB Output is correct
25 Correct 14 ms 14720 KB Output is correct
26 Correct 14 ms 14592 KB Output is correct
27 Correct 14 ms 14592 KB Output is correct
28 Correct 14 ms 14720 KB Output is correct
29 Correct 14 ms 14720 KB Output is correct
30 Correct 14 ms 14720 KB Output is correct
31 Correct 13 ms 14720 KB Output is correct
32 Correct 14 ms 14720 KB Output is correct
33 Correct 13 ms 14720 KB Output is correct
34 Correct 13 ms 14592 KB Output is correct
35 Correct 14 ms 14720 KB Output is correct
36 Correct 13 ms 14720 KB Output is correct
37 Correct 13 ms 14592 KB Output is correct
38 Correct 13 ms 14592 KB Output is correct

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 14464 KB Output is correct
2 Correct 12 ms 14464 KB Output is correct
3 Correct 13 ms 14464 KB Output is correct
4 Correct 13 ms 14464 KB Output is correct
5 Correct 13 ms 14464 KB Output is correct
6 Correct 13 ms 14464 KB Output is correct
7 Correct 13 ms 14464 KB Output is correct
8 Correct 13 ms 14464 KB Output is correct
9 Correct 13 ms 14464 KB Output is correct
10 Correct 13 ms 14464 KB Output is correct
11 Correct 13 ms 14464 KB Output is correct
12 Correct 13 ms 14464 KB Output is correct
13 Correct 13 ms 14464 KB Output is correct
14 Correct 13 ms 14592 KB Output is correct
15 Correct 14 ms 14464 KB Output is correct
16 Correct 12 ms 14464 KB Output is correct
17 Correct 13 ms 14464 KB Output is correct
18 Correct 13 ms 14464 KB Output is correct
19 Correct 146 ms 33784 KB Output is correct
20 Correct 142 ms 33656 KB Output is correct
21 Correct 141 ms 33272 KB Output is correct
22 Correct 150 ms 32120 KB Output is correct
23 Correct 103 ms 29432 KB Output is correct
24 Correct 104 ms 29944 KB Output is correct
25 Correct 127 ms 35704 KB Output is correct
26 Correct 100 ms 43768 KB Output is correct
27 Correct 189 ms 33912 KB Output is correct
28 Correct 286 ms 72932 KB Output is correct
29 Correct 283 ms 70520 KB Output is correct
30 Correct 196 ms 33912 KB Output is correct
31 Correct 209 ms 33912 KB Output is correct
32 Correct 238 ms 34040 KB Output is correct
33 Correct 211 ms 39032 KB Output is correct
34 Correct 215 ms 39032 KB Output is correct

Subtask #4
57.0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 14464 KB Output is correct
2 Correct 12 ms 14464 KB Output is correct
3 Correct 13 ms 14464 KB Output is correct
4 Correct 13 ms 14464 KB Output is correct
5 Correct 13 ms 14464 KB Output is correct
6 Correct 13 ms 14464 KB Output is correct
7 Correct 13 ms 14464 KB Output is correct
8 Correct 13 ms 14464 KB Output is correct
9 Correct 13 ms 14464 KB Output is correct
10 Correct 13 ms 14464 KB Output is correct
11 Correct 13 ms 14464 KB Output is correct
12 Correct 13 ms 14464 KB Output is correct
13 Correct 13 ms 14464 KB Output is correct
14 Correct 13 ms 14592 KB Output is correct
15 Correct 14 ms 14464 KB Output is correct
16 Correct 12 ms 14464 KB Output is correct
17 Correct 13 ms 14464 KB Output is correct
18 Correct 13 ms 14464 KB Output is correct
19 Correct 12 ms 14464 KB Output is correct
20 Correct 12 ms 14464 KB Output is correct
21 Correct 13 ms 14592 KB Output is correct
22 Correct 13 ms 14592 KB Output is correct
23 Correct 13 ms 14592 KB Output is correct
24 Correct 14 ms 14592 KB Output is correct
25 Correct 14 ms 14720 KB Output is correct
26 Correct 14 ms 14592 KB Output is correct
27 Correct 14 ms 14592 KB Output is correct
28 Correct 14 ms 14720 KB Output is correct
29 Correct 14 ms 14720 KB Output is correct
30 Correct 14 ms 14720 KB Output is correct
31 Correct 13 ms 14720 KB Output is correct
32 Correct 14 ms 14720 KB Output is correct
33 Correct 13 ms 14720 KB Output is correct
34 Correct 13 ms 14592 KB Output is correct
35 Correct 14 ms 14720 KB Output is correct
36 Correct 13 ms 14720 KB Output is correct
37 Correct 13 ms 14592 KB Output is correct
38 Correct 13 ms 14592 KB Output is correct
39 Correct 146 ms 33784 KB Output is correct
40 Correct 142 ms 33656 KB Output is correct
41 Correct 141 ms 33272 KB Output is correct
42 Correct 150 ms 32120 KB Output is correct
43 Correct 103 ms 29432 KB Output is correct
44 Correct 104 ms 29944 KB Output is correct
45 Correct 127 ms 35704 KB Output is correct
46 Correct 100 ms 43768 KB Output is correct
47 Correct 189 ms 33912 KB Output is correct
48 Correct 286 ms 72932 KB Output is correct
49 Correct 283 ms 70520 KB Output is correct
50 Correct 196 ms 33912 KB Output is correct
51 Correct 209 ms 33912 KB Output is correct
52 Correct 238 ms 34040 KB Output is correct
53 Correct 211 ms 39032 KB Output is correct
54 Correct 215 ms 39032 KB Output is correct
55 Correct 26 ms 17152 KB Output is correct
56 Correct 21 ms 16128 KB Output is correct
57 Correct 91 ms 31480 KB Output is correct
58 Correct 58 ms 22124 KB Output is correct
59 Correct 97 ms 45176 KB Output is correct
60 Correct 269 ms 73852 KB Output is correct
61 Correct 222 ms 38776 KB Output is correct
62 Correct 222 ms 38904 KB Output is correct
63 Correct 267 ms 38888 KB Output is correct
64 Correct 460 ms 93176 KB Output is correct
65 Correct 259 ms 41704 KB Output is correct
66 Correct 265 ms 66552 KB Output is correct
67 Correct 180 ms 29924 KB Output is correct
68 Correct 330 ms 51960 KB Output is correct
69 Correct 344 ms 52216 KB Output is correct
70 Correct 338 ms 50552 KB Output is correct