oj.uz

답안 #367136

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
367136 2021-02-16T10:48:38 Z idk321 꿈 (IOI13_dreaming) C++11
0 / 100
 167 ms 65536 KB 
    #include "dreaming.h"

    #include <bits/stdc++.h>
    using namespace std;

    int n, m, l;
    const int N =100005;
    bool vis[N];
    multiset<int> ms[N];
    vector<array<int, 2>> adj[N];
    vector<array<int, 2>> comp;

    int dfs1(int node, int par)
    {
        vis[node] = true;
        int res = 0;
        ms[node].insert(0);
        for (auto next : adj[node])
        {
            if (next[0] == par) continue;
            int cur = dfs1(next[0], node) + next[1];
            res = max(res, cur);
            ms[node].insert(cur);
        }

        return res;
    }

    int dfs2(int node, int par, int pdist)
    {

        if (par != -1)
        {
            int del = *ms[node].rbegin() + pdist;
            ms[par].erase(ms[par].find(del));
            ms[node].insert(*ms[par].rbegin() + pdist);
            ms[par].insert(del);
        }
        int res = *ms[node].rbegin();


        for (auto next : adj[node])
        {

            if (next[0] == par) continue;

            res = min(res, dfs2(next[0], node, next[1]));
        }


        return res;
    }

    array<int, 2> dfs3(int node, int par)
    {
        array<int, 2> best = {node, 0};
        for (auto next : adj[node])
        {
            if (next[0] == par) continue;
            auto cur = dfs3(next[0],node);
            cur[1] += next[1];
            if (cur[1] > best[1])
            {
                best = cur;
            }
        }

        return best;
    }

    int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
        n = N;
        m = M;
        l = L;
        for (int i = 0; i < m; i++)
        {

            adj[A[i]].push_back({B[i], T[i]});
            adj[B[i]].push_back({A[i], T[i]});
        }

        int res = 0;
        vector<int> cents;
        for (int i = 0; i < n; i++)
        {
            if (!vis[i])
            {
                dfs1(i, -1);
                int cent = dfs2(i, -1, -1);
                auto cur = dfs3(i, -1);
                int mdist = dfs3(cur[0], -1)[1];
                res = max(res, mdist);
                cents.push_back(cent);
                comp.push_back({cent, mdist});
            }
        }

        sort(cents.rbegin(), cents.rend());
        if (m == n -1) cout << res << "\n";
        else if (m == n - 2)
        {
            res = max(res, cents[0] + cents[1] + l);
            cout << res << "\n";
        } else
        {
            res = max(res, cents[0] + cents[1] + l);
            res = max(res, cents[1] + cents[2] + 2 * l);
            cout << res << "\n";
        }
    }

Compilation message

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:110:5: warning: no return statement in function returning non-void [-Wreturn-type]
  110 |     }
      |     ^

Subtask #1
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 167 ms 65536 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 17 ms 14956 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 167 ms 65536 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 67 ms 35440 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 17 ms 14956 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 167 ms 65536 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -