oj.uz

Submission #293197

# Submission time Handle Problem Language Result Execution time Memory
293197 2020-09-07T18:11:16 Z alexandra_udristoiu Dreaming (IOI13_dreaming) C++14
0 / 100
 60 ms 11516 KB 
#include "dreaming.h"
#include<algorithm>
#include<vector>
#define DIM 100005
#define f first
#define s second
using namespace std;
static int viz[DIM], w[DIM], df[DIM], d[DIM][2], nr;
static vector< pair<int, int> > v[DIM];
static void dfs1(int nod){
    viz[nod] = 1;
    d[nod][0] = d[nod][1] = 0;
    for(int i = 0; i < v[nod].size(); i++){
        int vecin = v[nod][i].f;
        if(viz[vecin] == 0){
            dfs1(vecin);
            if(d[vecin][0] + v[nod][i].s > d[nod][0]){
                d[nod][1] = d[nod][0];
                d[nod][0] = d[vecin][0] + v[nod][i].s;
            }
            else{
                d[nod][1] = max(d[nod][1], d[vecin][0] + v[nod][i].s);
            }
        }
    }
}
static void dfs2(int nod){
    viz[nod] = 2;
    for(int i = 0; i < v[nod].size(); i++){
        int vecin = v[nod][i].f;
        if(viz[vecin] == 1){
            df[vecin] = df[nod] + v[nod][i].s;
            if(d[nod][0] != d[vecin][0] + v[nod][i].s){
                df[vecin] = max(df[vecin], d[nod][0] + v[nod][i].s);
            }
            else{
                df[vecin] = max(df[vecin], d[nod][1] + v[nod][i].s);
            }
            w[nr] = min(w[nr], max(d[vecin][0], df[vecin]) );
            dfs2(vecin);
        }
    }
}

int travelTime(int n, int m, int k, int a[], int b[], int t[]) {
    int i, sol;
    for(i = 0; i < m; i++){
        v[ a[i] ].push_back( make_pair(b[i], t[i]) );
        v[ b[i] ].push_back( make_pair(a[i], t[i]) );
    }
    for(i = 0; i < n; i++){
        if(viz[i] == 0){
            dfs1(i);
        }
    }
    for(i = 0; i < n; i++){
        if(viz[i] == 1){
            nr++;
            w[nr] = d[i][0];
            dfs2(i);
        }
    }
    sort(w + 1, w + nr + 1);
    sol = max(w[nr] + w[nr - 1] + k, w[nr - 1] + w[nr - 2] + 2 * k);
    for(i = 0; i < n; i++){
        sol = max(sol, d[i][0] + d[i][1]);
    }
    return sol;
}

Compilation message

dreaming.cpp: In function 'void dfs1(int)':
dreaming.cpp:13:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |     for(int i = 0; i < v[nod].size(); i++){
      |                    ~~^~~~~~~~~~~~~~~
dreaming.cpp: In function 'void dfs2(int)':
dreaming.cpp:29:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for(int i = 0; i < v[nod].size(); i++){
      |                    ~~^~~~~~~~~~~~~~~

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 10360 KB Output is correct
2 Correct 60 ms 11516 KB Output is correct
3 Correct 41 ms 9592 KB Output is correct
4 Correct 9 ms 3968 KB Output is correct
5 Correct 8 ms 3584 KB Output is correct
6 Correct 16 ms 4608 KB Output is correct
7 Incorrect 2 ms 2688 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 10360 KB Output is correct
2 Correct 60 ms 11516 KB Output is correct
3 Correct 41 ms 9592 KB Output is correct
4 Correct 9 ms 3968 KB Output is correct
5 Correct 8 ms 3584 KB Output is correct
6 Correct 16 ms 4608 KB Output is correct
7 Incorrect 2 ms 2688 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 10360 KB Output is correct
2 Correct 60 ms 11516 KB Output is correct
3 Correct 41 ms 9592 KB Output is correct
4 Correct 9 ms 3968 KB Output is correct
5 Correct 8 ms 3584 KB Output is correct
6 Correct 16 ms 4608 KB Output is correct
7 Incorrect 2 ms 2688 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 6656 KB Output is correct
2 Correct 32 ms 6672 KB Output is correct
3 Correct 33 ms 6780 KB Output is correct
4 Correct 30 ms 6656 KB Output is correct
5 Correct 27 ms 6656 KB Output is correct
6 Correct 31 ms 6904 KB Output is correct
7 Correct 30 ms 6912 KB Output is correct
8 Correct 28 ms 6648 KB Output is correct
9 Correct 32 ms 6648 KB Output is correct
10 Correct 32 ms 6776 KB Output is correct
11 Correct 2 ms 2664 KB Output is correct
12 Correct 6 ms 4608 KB Output is correct
13 Correct 6 ms 4608 KB Output is correct
14 Correct 5 ms 4608 KB Output is correct
15 Correct 5 ms 4608 KB Output is correct
16 Correct 6 ms 4608 KB Output is correct
17 Correct 5 ms 4352 KB Output is correct
18 Correct 6 ms 4608 KB Output is correct
19 Correct 5 ms 4480 KB Output is correct
20 Incorrect 2 ms 2688 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 10360 KB Output is correct
2 Correct 60 ms 11516 KB Output is correct
3 Correct 41 ms 9592 KB Output is correct
4 Correct 9 ms 3968 KB Output is correct
5 Correct 8 ms 3584 KB Output is correct
6 Correct 16 ms 4608 KB Output is correct
7 Incorrect 2 ms 2688 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 10360 KB Output is correct
2 Correct 60 ms 11516 KB Output is correct
3 Correct 41 ms 9592 KB Output is correct
4 Correct 9 ms 3968 KB Output is correct
5 Correct 8 ms 3584 KB Output is correct
6 Correct 16 ms 4608 KB Output is correct
7 Incorrect 2 ms 2688 KB Output isn't correct
8 Halted 0 ms 0 KB -