oj.uz

Submission #29421

# Submission time Handle Problem Language Result Execution time Memory
29421 2017-07-19T10:27:55 Z Nikefor Race (IOI11_race) C++
9 / 100
 3000 ms 19952 KB 
#include "race.h"
#include<bits/stdc++.h>
#define inf 1<<22
using namespace std;
int globalMin = inf;
int target;
int W[1000001];
set<int> used;
vector< pair<int,int> > adj[200001];
void centroid(int n);
int sizer(int n, int road) {
    int sum = 0;
    for(int i=0; i<adj[n].size(); i++) {
        if(used.find(adj[n][i].first)==used.end() and (adj[n][i].second!=road)) sum+=sizer(adj[n][i].first, adj[n][i].second);
    }
    return sum+1;

}
int best_path(int N, int K, int H[][2], int L[])
{
    target = K;
    for(int i=0; i<N-1; i++) {
        int v1 = H[i][0], v2 = H[i][1];
        adj[v1].push_back(make_pair(v2, i));
        adj[v2].push_back(make_pair(v1, i));
    }
    for(int i=0; i<N-1; i++) W[i] = L[i];
    centroid(0);
    return globalMin<inf?globalMin:-1;
}
int A[200002];
int tmp[200002];
void DFS(int c, int road, int cost, int edge) {
    if(tmp[cost]>edge) tmp[cost] = edge;
    if(tmp[cost]+A[target-cost]<globalMin) globalMin = tmp[cost]+A[target-cost];
    for(int i =0; i< adj[c].size(); i++) {
        if(used.find(adj[c][i].first)!=used.end()) continue;
        if(adj[c][i].second!=road and ((cost+W[adj[c][i].second])<=target) ) DFS(adj[c][i].first, adj[c][i].second, cost+W[adj[c][i].second], edge+1);
    }

}
void centroid(int n) {
    if( sizer(n, -1)<2 ) return;
   // int c = centroidibul(int n);
    int c = n;
    int kol = adj[c].size();

    for(int i=1; i<target+1; i++) A[i] = tmp[i] = inf;
    A[0] = tmp[0]=0;
    for(int i= 0; i<kol; i++) {
        if(used.find(adj[c][i].first)!=used.end() ) continue;
        for(int j=1; j<=target; j++) tmp[j] = inf;
        if(W[adj[c][i].second] <= target )DFS(adj[c][i].first, adj[c][i].second, W[adj[c][i].second], 1);
      //  for(int j=1; j<target; j++) if((tmp[j]+A[target-j])<globalMin) globalMin = tmp[j]+A[target-j];
        for(int j=1; j<target; j++) if(tmp[j]<A[j]) A[j] = tmp[j];

    }
    used.insert(c);
    for(int i=0; i<kol; i++) if(used.find(adj[c][i].first)==used.end() ) centroid(adj[c][i].first);

}

Compilation message

race.cpp: In function 'int sizer(int, int)':
race.cpp:13:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<adj[n].size(); i++) {
                  ~^~~~~~~~~~~~~~
race.cpp: In function 'void DFS(int, int, int, int)':
race.cpp:36:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i =0; i< adj[c].size(); i++) {
                   ~^~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 5212 KB Output is correct
3 Correct 6 ms 5212 KB Output is correct
4 Correct 7 ms 5212 KB Output is correct
5 Correct 5 ms 5212 KB Output is correct
6 Correct 6 ms 5212 KB Output is correct
7 Correct 6 ms 5212 KB Output is correct
8 Correct 7 ms 5264 KB Output is correct
9 Correct 6 ms 5264 KB Output is correct
10 Correct 6 ms 5272 KB Output is correct
11 Correct 7 ms 5272 KB Output is correct
12 Correct 6 ms 5272 KB Output is correct
13 Correct 7 ms 5332 KB Output is correct
14 Correct 8 ms 5332 KB Output is correct
15 Correct 7 ms 5332 KB Output is correct
16 Correct 7 ms 5332 KB Output is correct
17 Correct 8 ms 5332 KB Output is correct
18 Correct 7 ms 5332 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 5212 KB Output is correct
3 Correct 6 ms 5212 KB Output is correct
4 Correct 7 ms 5212 KB Output is correct
5 Correct 5 ms 5212 KB Output is correct
6 Correct 6 ms 5212 KB Output is correct
7 Correct 6 ms 5212 KB Output is correct
8 Correct 7 ms 5264 KB Output is correct
9 Correct 6 ms 5264 KB Output is correct
10 Correct 6 ms 5272 KB Output is correct
11 Correct 7 ms 5272 KB Output is correct
12 Correct 6 ms 5272 KB Output is correct
13 Correct 7 ms 5332 KB Output is correct
14 Correct 8 ms 5332 KB Output is correct
15 Correct 7 ms 5332 KB Output is correct
16 Correct 7 ms 5332 KB Output is correct
17 Correct 8 ms 5332 KB Output is correct
18 Correct 7 ms 5332 KB Output is correct
19 Correct 6 ms 5332 KB Output is correct
20 Correct 8 ms 5332 KB Output is correct
21 Correct 11 ms 5348 KB Output is correct
22 Runtime error 16 ms 13284 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 5212 KB Output is correct
3 Correct 6 ms 5212 KB Output is correct
4 Correct 7 ms 5212 KB Output is correct
5 Correct 5 ms 5212 KB Output is correct
6 Correct 6 ms 5212 KB Output is correct
7 Correct 6 ms 5212 KB Output is correct
8 Correct 7 ms 5264 KB Output is correct
9 Correct 6 ms 5264 KB Output is correct
10 Correct 6 ms 5272 KB Output is correct
11 Correct 7 ms 5272 KB Output is correct
12 Correct 6 ms 5272 KB Output is correct
13 Correct 7 ms 5332 KB Output is correct
14 Correct 8 ms 5332 KB Output is correct
15 Correct 7 ms 5332 KB Output is correct
16 Correct 7 ms 5332 KB Output is correct
17 Correct 8 ms 5332 KB Output is correct
18 Correct 7 ms 5332 KB Output is correct
19 Correct 1694 ms 19952 KB Output is correct
20 Correct 1702 ms 19952 KB Output is correct
21 Correct 1422 ms 19952 KB Output is correct
22 Correct 819 ms 19952 KB Output is correct
23 Correct 682 ms 19952 KB Output is correct
24 Correct 278 ms 19952 KB Output is correct
25 Execution timed out 3051 ms 19952 KB Time limit exceeded
26 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 5212 KB Output is correct
3 Correct 6 ms 5212 KB Output is correct
4 Correct 7 ms 5212 KB Output is correct
5 Correct 5 ms 5212 KB Output is correct
6 Correct 6 ms 5212 KB Output is correct
7 Correct 6 ms 5212 KB Output is correct
8 Correct 7 ms 5264 KB Output is correct
9 Correct 6 ms 5264 KB Output is correct
10 Correct 6 ms 5272 KB Output is correct
11 Correct 7 ms 5272 KB Output is correct
12 Correct 6 ms 5272 KB Output is correct
13 Correct 7 ms 5332 KB Output is correct
14 Correct 8 ms 5332 KB Output is correct
15 Correct 7 ms 5332 KB Output is correct
16 Correct 7 ms 5332 KB Output is correct
17 Correct 8 ms 5332 KB Output is correct
18 Correct 7 ms 5332 KB Output is correct
19 Correct 6 ms 5332 KB Output is correct
20 Correct 8 ms 5332 KB Output is correct
21 Correct 11 ms 5348 KB Output is correct
22 Runtime error 16 ms 13284 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Halted 0 ms 0 KB -