oj.uz

Submission #492177

# Submission time Handle Problem Language Result Execution time Memory
492177 2021-12-05T20:21:51 Z aci Dreaming (IOI13_dreaming) C++14
0 / 100
 69 ms 15684 KB 
#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
#define INF 1000000000
typedef long long ll;
typedef pair<ll, ll> pi;

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


int n, m, l;
ll 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; //diametro massimo e profondità

    for (int i=0; i<n; i++)
    {
        
        if(!used[i])
        {
            
            dist[i].first =0;//parto nodo a caso
            el.clear(); 
            dfs1(i, i);
            
            used2.assign(n, 0); //rifaccio dfs
            int ind=i, mx = 0;
            
            //cerco nodo a distanza massima 
            for (int j : el)
            {
                if(dist[j].first > mx)
                {
                    mx = dist[j].first;
                    ind = j;
                }
            }


            dist[ind].second = 0;
            dfs2(ind, ind);
            
            d = 0;
            //trovo diamentro e suoi estremi
            for (int j : el)
            {
                if(dist[j].second > d)
                {
                    d = dist[j].second;
                    ind = j;
                }
            }
            //rifaccio fs anche su altro estremo
            used2.assign(n, 0);
            dist[ind].first = 0;
            r = INF;
            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);
    long long res = 0;
    for (auto x : comp) res = max(res, x.first); 
    res = max(res, max(ll(comp[0].second+l+comp[1].second), ll(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 69 ms 15684 KB Output is correct
2 Correct 67 ms 15564 KB Output is correct
3 Correct 41 ms 10448 KB Output is correct
4 Correct 7 ms 2636 KB Output is correct
5 Correct 7 ms 1868 KB Output is correct
6 Correct 16 ms 3912 KB Output is correct
7 Incorrect 1 ms 296 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 1 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 69 ms 15684 KB Output is correct
2 Correct 67 ms 15564 KB Output is correct
3 Correct 41 ms 10448 KB Output is correct
4 Correct 7 ms 2636 KB Output is correct
5 Correct 7 ms 1868 KB Output is correct
6 Correct 16 ms 3912 KB Output is correct
7 Incorrect 1 ms 296 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 60 ms 14972 KB Execution killed with signal 11
2 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 1 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 69 ms 15684 KB Output is correct
2 Correct 67 ms 15564 KB Output is correct
3 Correct 41 ms 10448 KB Output is correct
4 Correct 7 ms 2636 KB Output is correct
5 Correct 7 ms 1868 KB Output is correct
6 Correct 16 ms 3912 KB Output is correct
7 Incorrect 1 ms 296 KB Output isn't correct
8 Halted 0 ms 0 KB -