oj.uz

Submission #962204

# Submission time Handle Problem Language Result Execution time Memory
962204 2024-04-13T08:54:45 Z n3rm1n Dreaming (IOI13_dreaming) C++17
14 / 100
 90 ms 37900 KB 
#include<bits/stdc++.h>
#include "dreaming.h"
using namespace std;
const long long MAXN = 5e5 + 10;
vector < pair < long long, long long > > g[MAXN];
long long mark[MAXN];
long long used[MAXN];
void dfs0(long long beg)
{
    mark[beg] = 1;
    used[beg] = 1;
    long long nb;
    for (long long i = 0; i < g[beg].size(); ++ i)
    {
        nb = g[beg][i].first;
        if(!used[nb])
            dfs0(nb);
    }
}
long long far = 0, far_index;
void dfs_diam(int beg, int to_there)
{
    if(far < to_there)
    {
        far = to_there;
        far_index = beg;
    }
    used[beg] = 1;
    int nb, distt;
    for (int i = 0; i < g[beg].size(); ++ i)
    {
        nb = g[beg][i].first;
        distt = g[beg][i].second;
        if(!used[nb])dfs_diam(nb, to_there + distt);
    }
}
long long maxdist = 0;
long long dfs(long long beg)
{
    used[beg] = 1;
    long long nb, distt;
    long long maxx = 0;
    for (long long i = 0; i < g[beg].size(); ++ i)
    {
        nb = g[beg][i].first;
        distt = g[beg][i].second;
        if(!used[nb])maxx = max(maxx, dfs(nb)+distt);
    }
    return maxx;
}
vector < pair < long long, long long >  > path;
long long st, fi;
long long dfs_form(long long beg, long long add)
{
    used[beg] = 1;
    if(beg == fi)
    {
        path.push_back(make_pair(beg, add));
        return 1;
    }
    long long nb, distt;
    long long found = 0;
    for (long long i = 0; i < g[beg].size(); ++ i)
    {
        nb = g[beg][i].first;
        distt = g[beg][i].second;
        if(!used[nb])
        {
            if(dfs_form(nb, add + distt))found = 1;
        }
    }
    if(found)path.push_back(make_pair(beg, add));
    return found;
}
vector < pair < long long, long long > > path1, path2;
int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
    for (long long i = 0; i < M; ++ i)
    {
        g[A[i]].push_back(make_pair(B[i], T[i]));
        g[B[i]].push_back(make_pair(A[i], T[i]));
    }

    long long n = N;
    dfs0(0);

    /// opit
    int aa1 = 0, bb1 = 0;
    int aa2 = 0, bb2 = 0;
    memset(used, 0, sizeof(used));
    far = 0;
    far_index = 0;
    dfs_diam(0, 0);
    aa1 = far_index;
    memset(used, 0, sizeof(used));
    far = 0;
    far_index = 0;
    dfs_diam(aa1, 0);
    bb1 = far_index;

    int starter2 = -1;
    for (int i = 0; i < n && (starter2 == -1); ++ i)
        if(!mark[i])starter2 = i;
    memset(used, 0, sizeof(used));
    far = 0;
    far_index = 0;
    dfs_diam(starter2, 0);
    aa2 = far_index;
    memset(used, 0, sizeof(used));
    far = 0;
    far_index = 0;
    dfs_diam(aa2, 0);
    bb2 = far_index;

    path.clear();
    st = aa1;
    fi = bb1;
    dfs_form(st, 0);
    memset(used, 0, sizeof(used));
    path1 = path;
    path.clear();
    st = aa2;
    fi = bb2;
    memset(used, 0, sizeof(used));
    dfs_form(st, 0);
    path2 = path;

    long long index1 = path1[0].first, index2 = path2[0].first;
    long long total1 = path1[0].second;
    long long total2 = path2[0].second;
    long long best1 = total1, best2 = total2, curr;
    for (int i = 1; i < path1.size(); ++ i)
    {
        curr = max(path1[i].second, total1 - path1[i].second);
        if(curr < best1)
        {
            best1 = curr;
            index1 = path1[i].first;
        }
    }
    for (int i = 1; i < path2.size(); ++ i)
    {
        curr = max(path2[i].second, total2 - path2[i].second);

        if(curr < best2)
        {
            best2 = curr;
            index2 = path2[i].first;
        }
    }
    g[index1].push_back(make_pair(index2, L));
    g[index2].push_back(make_pair(index1, L));
    long long ans = 0;
    memset(used, 0, sizeof(used));
    ans = max(ans, dfs(aa1));
    memset(used, 0, sizeof(used));
    ans = max(ans, dfs(bb1));
    memset(used, 0, sizeof(used));
    ans = max(ans, dfs(aa2));
    memset(used, 0, sizeof(used));
    ans = max(ans, dfs(bb2));
    return ans;
    ///

}

Compilation message

dreaming.cpp: In function 'void dfs0(long long int)':
dreaming.cpp:13:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |     for (long long i = 0; i < g[beg].size(); ++ i)
      |                           ~~^~~~~~~~~~~~~~~
dreaming.cpp: In function 'void dfs_diam(int, int)':
dreaming.cpp:30:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for (int i = 0; i < g[beg].size(); ++ i)
      |                     ~~^~~~~~~~~~~~~~~
dreaming.cpp: In function 'long long int dfs(long long int)':
dreaming.cpp:43:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for (long long i = 0; i < g[beg].size(); ++ i)
      |                           ~~^~~~~~~~~~~~~~~
dreaming.cpp: In function 'long long int dfs_form(long long int, long long int)':
dreaming.cpp:63:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     for (long long i = 0; i < g[beg].size(); ++ i)
      |                           ~~^~~~~~~~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:132:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |     for (int i = 1; i < path1.size(); ++ i)
      |                     ~~^~~~~~~~~~~~~~
dreaming.cpp:141:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  141 |     for (int i = 1; i < path2.size(); ++ i)
      |                     ~~^~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 36288 KB Output is correct
2 Correct 68 ms 36548 KB Output is correct
3 Correct 40 ms 30660 KB Output is correct
4 Correct 11 ms 21468 KB Output is correct
5 Correct 12 ms 20316 KB Output is correct
6 Correct 21 ms 22864 KB Output is correct
7 Correct 4 ms 18780 KB Output is correct
8 Correct 32 ms 25044 KB Output is correct
9 Correct 42 ms 27500 KB Output is correct
10 Correct 5 ms 19032 KB Output is correct
11 Correct 66 ms 29756 KB Output is correct
12 Correct 90 ms 33184 KB Output is correct
13 Correct 5 ms 19032 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 22 ms 37900 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 36288 KB Output is correct
2 Correct 68 ms 36548 KB Output is correct
3 Correct 40 ms 30660 KB Output is correct
4 Correct 11 ms 21468 KB Output is correct
5 Correct 12 ms 20316 KB Output is correct
6 Correct 21 ms 22864 KB Output is correct
7 Correct 4 ms 18780 KB Output is correct
8 Correct 32 ms 25044 KB Output is correct
9 Correct 42 ms 27500 KB Output is correct
10 Correct 5 ms 19032 KB Output is correct
11 Correct 66 ms 29756 KB Output is correct
12 Correct 90 ms 33184 KB Output is correct
13 Correct 5 ms 19032 KB Output is correct
14 Runtime error 22 ms 37900 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 20824 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 22 ms 37900 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 36288 KB Output is correct
2 Correct 68 ms 36548 KB Output is correct
3 Correct 40 ms 30660 KB Output is correct
4 Correct 11 ms 21468 KB Output is correct
5 Correct 12 ms 20316 KB Output is correct
6 Correct 21 ms 22864 KB Output is correct
7 Correct 4 ms 18780 KB Output is correct
8 Correct 32 ms 25044 KB Output is correct
9 Correct 42 ms 27500 KB Output is correct
10 Correct 5 ms 19032 KB Output is correct
11 Correct 66 ms 29756 KB Output is correct
12 Correct 90 ms 33184 KB Output is correct
13 Correct 5 ms 19032 KB Output is correct
14 Runtime error 22 ms 37900 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -