oj.uz

Submission #245451

# Submission time Handle Problem Language Result Execution time Memory
245451 2020-07-06T13:20:37 Z gratus907 Dreaming (IOI13_dreaming) C++17
0 / 100
 1000 ms 12276 KB 
#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
#define ll long long
#define all(x) ((x).begin()),((x).end())
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using pii=pair<int, int>;
vector <pii> Graph[101010];
int n, m;
bool vst[101010];
bool dfs_visit[101010];
vector <pii> radii; 
vector <int> cur_tree;
pii dist_bfs(vector <int> &par, vector<int> &dt, int root, vector<int> &Tr)
{
    vector <bool> tmpvisit(101010, false);
    queue <int> q;
    q.push(root);
    dt[root] = 0;
    par[root] = -1;
    tmpvisit[root] = true;
    while(!q.empty())
    {
        int x = q.front();
        q.pop();
        for (auto it:Graph[x])
        {
            if (!tmpvisit[it.first])
            {
                dt[it.first] = dt[x]+it.second;
                tmpvisit[it.first] = true;
                q.push(it.first);
                par[it.first] = x;
            }
        }
    }
    int maxdist = 0, maxdistpoint = 0;
    for (auto nd : Tr)
    {
        if (dt[nd] >= maxdist)
        {
            maxdist = dt[nd];
            maxdistpoint = nd;
        }
    }
    return {maxdist, maxdistpoint};
}

void dfs(int r, int p)
{
    cur_tree.push_back(r);
    dfs_visit[r] = true;
    for (auto it:Graph[r])
    {
        if (!dfs_visit[it.first])
        {
            if (it.first != p)
            {
                dfs(it.first, r);
            }
        }
    }
}
pii decomp_tree(int root)
{
    vector<int> dt(101010, 1e8);
    vector<int> par(101010, 0);
    pii p1 = dist_bfs(par, dt, root, cur_tree);
    par.clear();
    par.resize(101010, 0);
    dt.clear();
    dt.resize(101010, 1e8);
    pii p2 = dist_bfs(par, dt, p1.second, cur_tree);
    int A = p1.second, B = p2.second;
    int p = B;
    vector <int> TT; 
    while(p!=-1)
    {
        TT.push_back(p);
        p = par[p];
    }
    vector <int> RR;
    int R = INT_MAX;
    for (auto it:TT)
        R = min(R, max(dt[it], dt[B]-dt[it]));
    return {R, dt[B]};
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) 
{
    n = N, m = M;
    for (int i = 0; i<M; i++)
    {
        Graph[A[i]].push_back({B[i],T[i]});
        Graph[B[i]].push_back({A[i],T[i]});
    }
    for (int i = 0; i<N; i++)
    {
        if (vst[i]) continue;
        memset(dfs_visit, 0, sizeof(dfs_visit));
        cur_tree.clear();
        dfs(i, -1);
        for (auto it:cur_tree)
            vst[it] = true;
        radii.push_back(decomp_tree(i));
    }
//    for (auto it:radii)
//        printf("%d %d\n",it.first, it.second);
    sort(all(radii),greater<pii>());
    if (radii.size()==1)
    {
        return radii.front().second;
    }
    else
        return radii[0].first+radii[1].first+L;
}

Compilation message

dreaming.cpp: In function 'pii decomp_tree(int)':
dreaming.cpp:74:9: warning: unused variable 'A' [-Wunused-variable]
     int A = p1.second, B = p2.second;
         ^

Subtask #1
0 / 14.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 23.0

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

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1094 ms 7040 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

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