oj.uz

Submission #492114

# Submission time Handle Problem Language Result Execution time Memory
492114 2021-12-05T13:58:11 Z aci Dreaming (IOI13_dreaming) C++14
0 / 100
 74 ms 14000 KB 
#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
#define INF 1000000
typedef pair<int, int> pi;

vector<vector<pi>> t;
vector<bool> used;
vector<bool> used2;


int n, m, l;
int d, r;
vector<pi> dist;
vector<int> el;

void dfs1(int u, int p)
{
    used[u] = 1;
    el.push_back(u);
    for (pi v : t[u])
    {
        if(v.first!=p && !used[v.first])
        {
            dist[v.first].first = dist[u].first + v.second;
            dfs1(v.first, u);
        }
    }
}

void dfs2(int u, int p)
{
    used2[u] = 1;
    for (pi v : t[u])
    {
        if(v.first!=p && !used2[v.first])
        {
            dist[v.first].second = dist[u].second + v.second;
            dfs2(v.first, u);
        }
    }
}
void dfs3(int u, int p)
{
    used2[u] = 1;
    for (pi v : t[u])
    {
        if(v.first!=p && !used2[v.first])
        {
            dist[v.first].first = dist[u].first + v.second;
            dfs3(v.first, u);
        }
    }
}

bool cmp(pi a, pi b)
{
    return (a.second > b.second);
}


int travelTime(int N, int M, int L, int A[], int B[], int T[]) 
{
    
    n = N;
    m = M;
    l = L;

    t.resize(n);
    used.resize(n, 0);
    dist.resize(n, {-1, -1});
    used2.resize(n, 0);

    for (int i=0; i<m; i++)
    {
        int x, y, w;
        x = A[i];
        y = B[i];
        w = T[i];

        t[x].push_back({y, w});
        t[y].push_back({x, w});
    }
    vector<pi> comp;
    

    for (int i=0; i<n; i++)
    {
        
        if(!used[i])
        {
            
            dist[i].first =0;
            el.clear();
            dfs1(i, i);
            //cout<< endl;
            used2.assign(n, 0);
            int ind=i, mx = 0;
            d = 0;
            r = INF;
            for (int j : el)
            {
                if(dist[j].first > mx)
                {
                    mx = dist[j].first;
                    ind = j;
                }
            }

            dist[ind].second = 0;
            dfs2(ind, ind);
            
    
            for (int j : el)
            {
                if(dist[j].second > d)
                {
                    d = dist[j].second;
                    ind = j;
                }
            }
            used2.assign(n, 0);
            dist[ind].first = 0;
            dfs3(ind, ind);
            //for (int j : el) //cout<<j<<" "<< dist[j].first<<" "<<dist[j].second<<endl;
            for (int j : el)
            {
                if(dist[j].first==-1) dist[j].first = INF;
                if(dist[j].second==-1) dist[j].second = INF;
                r = min(r, max(dist[j].first, dist[j].second));
            }
            comp.push_back({d, r});

        }
    }
    sort(comp.begin(), comp.end(), cmp);
    int res = 0;
    for (auto x : comp) res = max(res, x.first);
    res = max(res, max(comp[0].second+l+comp[1].second, 2*l+comp[1].second+comp[2].second));

    //for (auto x : comp) //cout<< x.first<<" "<<x.second<<endl;


    return res;

}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 13920 KB Output is correct
2 Correct 46 ms 14000 KB Output is correct
3 Correct 31 ms 9544 KB Output is correct
4 Correct 7 ms 2380 KB Output is correct
5 Correct 6 ms 1484 KB Output is correct
6 Correct 15 ms 3532 KB Output is correct
7 Incorrect 1 ms 332 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 13920 KB Output is correct
2 Correct 46 ms 14000 KB Output is correct
3 Correct 31 ms 9544 KB Output is correct
4 Correct 7 ms 2380 KB Output is correct
5 Correct 6 ms 1484 KB Output is correct
6 Correct 15 ms 3532 KB Output is correct
7 Incorrect 1 ms 332 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 6532 KB Output is correct
2 Correct 57 ms 6680 KB Output is correct
3 Correct 54 ms 6540 KB Output is correct
4 Correct 57 ms 6596 KB Output is correct
5 Correct 59 ms 6616 KB Output is correct
6 Correct 58 ms 7472 KB Output is correct
7 Correct 62 ms 6920 KB Output is correct
8 Correct 62 ms 6552 KB Output is correct
9 Correct 52 ms 6412 KB Output is correct
10 Correct 66 ms 6756 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 66 ms 4532 KB Output is correct
13 Correct 64 ms 4568 KB Output is correct
14 Correct 63 ms 4592 KB Output is correct
15 Correct 64 ms 4648 KB Output is correct
16 Correct 63 ms 4536 KB Output is correct
17 Correct 63 ms 4540 KB Output is correct
18 Correct 66 ms 4684 KB Output is correct
19 Correct 74 ms 4600 KB Output is correct
20 Incorrect 0 ms 204 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 13920 KB Output is correct
2 Correct 46 ms 14000 KB Output is correct
3 Correct 31 ms 9544 KB Output is correct
4 Correct 7 ms 2380 KB Output is correct
5 Correct 6 ms 1484 KB Output is correct
6 Correct 15 ms 3532 KB Output is correct
7 Incorrect 1 ms 332 KB Output isn't correct
8 Halted 0 ms 0 KB -