oj.uz

Submission #336003

# Submission time Handle Problem Language Result Execution time Memory
336003 2020-12-14T13:17:02 Z blue Dreaming (IOI13_dreaming) C++11
14 / 100
 110 ms 13420 KB 
#include "dreaming.h"
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <queue>
using namespace std;

vector<int> edge[100001];
vector<int> weight[100001];
vector<int> edge_size(1e5 + 1, 0);
vector<int> maxdist(1e5 + 1, 0);
vector<int> visit(1e5 + 1, 0);
vector<int> roots;

struct distcomp
{
    int i;
};

bool operator < (distcomp A, distcomp B)
{
    if(maxdist[A.i] == maxdist[B.i]) return A.i < B.i;
    return maxdist[A.i] < maxdist[B.i];
}

int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
    for(int i = 0; i < M; i++)
    {
        edge[A[i]].push_back(B[i]);
        weight[A[i]].push_back(T[i]);
        edge_size[A[i]]++;

        edge[B[i]].push_back(A[i]);
        weight[B[i]].push_back(T[i]);
        edge_size[B[i]]++;
    }


    set<distcomp> tbv;
    for(int i = 0; i < N; i++)
    {
        if(edge_size[i] == 1) tbv.insert(distcomp{i});
    }

    int u, v, w;
    int flag;
    while(!tbv.empty())
    {
        u = tbv.begin()->i;
        tbv.erase(tbv.begin());
        visit[u] = 1;

        for(int i = 0; i < edge[u].size(); i++)
        {
            v = edge[u][i];
            w = weight[u][i];

            if(visit[v]) continue;
            edge_size[v]--;
            tbv.erase(distcomp{v});
            maxdist[v] = max(maxdist[v], maxdist[u] + w);
            tbv.insert(distcomp{v});
            flag = 0;
            if(edge_size[v] == 1)
            {
                tbv.insert(distcomp{v});
            }
        }
    }

    for(int i = 0; i < N; i++) if(edge_size[i] == 0)
    {
        roots.push_back(i);
    }

    int res = 0;
    int max1, max2;
    for(int r: roots)
    {
        max1 = max2 = 0;
        for(int i = 0; i < edge[r].size(); i++)
        {
            v = edge[r][i];
            w = weight[r][i];

            if(maxdist[v] + w >= max1)
            {
                max2 = max1;
                max1 = maxdist[v] + w;
            }
            else if(maxdist[v] + w >= max2) max2 = maxdist[v] + w;
        }
        res = max(res, max1 + max2);
    }

    for(int i = 0; i < roots.size(); i++) roots[i] = maxdist[roots[i]] * -1;
    sort(roots.begin(), roots.end());

    if(roots.size() >= 2) res = max(res, L - roots[0] - roots[1]);
    if(roots.size() >= 3) res = max(res, 2*L - roots[1] - roots[1]);

    return res;
}

Compilation message

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:55:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |         for(int i = 0; i < edge[u].size(); i++)
      |                        ~~^~~~~~~~~~~~~~~~
dreaming.cpp:83:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |         for(int i = 0; i < edge[r].size(); i++)
      |                        ~~^~~~~~~~~~~~~~~~
dreaming.cpp:98:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |     for(int i = 0; i < roots.size(); i++) roots[i] = maxdist[roots[i]] * -1;
      |                    ~~^~~~~~~~~~~~~~
dreaming.cpp:48:9: warning: variable 'flag' set but not used [-Wunused-but-set-variable]
   48 |     int flag;
      |         ^~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 13036 KB Output is correct
2 Correct 98 ms 12908 KB Output is correct
3 Correct 56 ms 10604 KB Output is correct
4 Correct 20 ms 7148 KB Output is correct
5 Correct 12 ms 6892 KB Output is correct
6 Correct 20 ms 7660 KB Output is correct
7 Correct 5 ms 6252 KB Output is correct
8 Correct 47 ms 9196 KB Output is correct
9 Correct 69 ms 9908 KB Output is correct
10 Correct 5 ms 6252 KB Output is correct
11 Correct 92 ms 11372 KB Output is correct
12 Correct 108 ms 12140 KB Output is correct
13 Correct 5 ms 6252 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 13036 KB Output is correct
2 Correct 98 ms 12908 KB Output is correct
3 Correct 56 ms 10604 KB Output is correct
4 Correct 20 ms 7148 KB Output is correct
5 Correct 12 ms 6892 KB Output is correct
6 Correct 20 ms 7660 KB Output is correct
7 Correct 5 ms 6252 KB Output is correct
8 Correct 47 ms 9196 KB Output is correct
9 Correct 69 ms 9908 KB Output is correct
10 Correct 5 ms 6252 KB Output is correct
11 Correct 92 ms 11372 KB Output is correct
12 Correct 108 ms 12140 KB Output is correct
13 Correct 5 ms 6252 KB Output is correct
14 Incorrect 5 ms 6252 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 13036 KB Output is correct
2 Correct 98 ms 12908 KB Output is correct
3 Correct 56 ms 10604 KB Output is correct
4 Correct 20 ms 7148 KB Output is correct
5 Correct 12 ms 6892 KB Output is correct
6 Correct 20 ms 7660 KB Output is correct
7 Correct 5 ms 6252 KB Output is correct
8 Correct 47 ms 9196 KB Output is correct
9 Correct 69 ms 9908 KB Output is correct
10 Correct 5 ms 6252 KB Output is correct
11 Correct 92 ms 11372 KB Output is correct
12 Correct 108 ms 12140 KB Output is correct
13 Correct 5 ms 6252 KB Output is correct
14 Incorrect 5 ms 6252 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 13420 KB Output is correct
2 Incorrect 107 ms 13420 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 13036 KB Output is correct
2 Correct 98 ms 12908 KB Output is correct
3 Correct 56 ms 10604 KB Output is correct
4 Correct 20 ms 7148 KB Output is correct
5 Correct 12 ms 6892 KB Output is correct
6 Correct 20 ms 7660 KB Output is correct
7 Correct 5 ms 6252 KB Output is correct
8 Correct 47 ms 9196 KB Output is correct
9 Correct 69 ms 9908 KB Output is correct
10 Correct 5 ms 6252 KB Output is correct
11 Correct 92 ms 11372 KB Output is correct
12 Correct 108 ms 12140 KB Output is correct
13 Correct 5 ms 6252 KB Output is correct
14 Correct 5 ms 6252 KB Output is correct
15 Correct 6 ms 6380 KB Output is correct
16 Correct 7 ms 6508 KB Output is correct
17 Incorrect 5 ms 6252 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 13036 KB Output is correct
2 Correct 98 ms 12908 KB Output is correct
3 Correct 56 ms 10604 KB Output is correct
4 Correct 20 ms 7148 KB Output is correct
5 Correct 12 ms 6892 KB Output is correct
6 Correct 20 ms 7660 KB Output is correct
7 Correct 5 ms 6252 KB Output is correct
8 Correct 47 ms 9196 KB Output is correct
9 Correct 69 ms 9908 KB Output is correct
10 Correct 5 ms 6252 KB Output is correct
11 Correct 92 ms 11372 KB Output is correct
12 Correct 108 ms 12140 KB Output is correct
13 Correct 5 ms 6252 KB Output is correct
14 Incorrect 5 ms 6252 KB Output isn't correct
15 Halted 0 ms 0 KB -