oj.uz

Submission #492116

# Submission time Handle Problem Language Result Execution time Memory
492116 2021-12-05T14:06:19 Z aci Dreaming (IOI13_dreaming) C++14
0 / 100
 92 ms 13184 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 43 ms 13184 KB Output is correct
2 Correct 46 ms 13180 KB Output is correct
3 Correct 29 ms 8796 KB Output is correct
4 Correct 10 ms 2252 KB Output is correct
5 Correct 8 ms 1356 KB Output is correct
6 Correct 15 ms 3148 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 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Incorrect 1 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 43 ms 13184 KB Output is correct
2 Correct 46 ms 13180 KB Output is correct
3 Correct 29 ms 8796 KB Output is correct
4 Correct 10 ms 2252 KB Output is correct
5 Correct 8 ms 1356 KB Output is correct
6 Correct 15 ms 3148 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 58 ms 6216 KB Output is correct
2 Correct 77 ms 6252 KB Output is correct
3 Correct 73 ms 6200 KB Output is correct
4 Correct 61 ms 6264 KB Output is correct
5 Correct 59 ms 6204 KB Output is correct
6 Correct 68 ms 6980 KB Output is correct
7 Correct 70 ms 6464 KB Output is correct
8 Correct 62 ms 6104 KB Output is correct
9 Correct 91 ms 5996 KB Output is correct
10 Correct 92 ms 6408 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 85 ms 4544 KB Output is correct
13 Correct 67 ms 4568 KB Output is correct
14 Correct 65 ms 4520 KB Output is correct
15 Correct 84 ms 4552 KB Output is correct
16 Correct 90 ms 4568 KB Output is correct
17 Correct 71 ms 4592 KB Output is correct
18 Correct 82 ms 4556 KB Output is correct
19 Correct 67 ms 4600 KB Output is correct
20 Incorrect 1 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 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Incorrect 1 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 43 ms 13184 KB Output is correct
2 Correct 46 ms 13180 KB Output is correct
3 Correct 29 ms 8796 KB Output is correct
4 Correct 10 ms 2252 KB Output is correct
5 Correct 8 ms 1356 KB Output is correct
6 Correct 15 ms 3148 KB Output is correct
7 Incorrect 1 ms 332 KB Output isn't correct
8 Halted 0 ms 0 KB -