oj.uz

답안 #167995

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
167995 2019-12-11T06:39:51 Z davitmarg 꿈 (IOI13_dreaming) C++17
14 / 100
 142 ms 25820 KB 
/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <unordered_map>
#include <set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#include <fstream>
#define mod 1000000000ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(), v.end()
using namespace std;

const int N = 100005;

#ifndef death
#include "dreaming.h"
#endif

int n, used[N], color;
LL x, ans[N], mx[N], lng[N];
vector<pair<int, LL>> g[N];
vector<LL> dp[N];

void dfs(int v)
{
    used[v] = color;
    dp[v].PB(0);
    dp[v].PB(0);
    for (int i = 0; i < g[v].size(); i++)
    {
        int to = g[v][i].first;
        LL d = g[v][i].second;
        if (used[to])
            continue;
        dfs(to);
        dp[v].PB(dp[to][0] + d);
        mx[v] = max(mx[v], mx[to]);
    }
    sort(all(dp[v]));
    reverse(all(dp[v]));
    mx[v] = dp[v][0] + dp[v][1];
}

void dfs2(int v, int p, LL dist)
{
    vector<LL> d;
    d.PB(dp[v][0]);
    d.PB(dp[v][1]);
    d.PB(dist);
    sort(all(d));
    reverse(all(d));

    lng[v] = d[0];
    ans[v] = max(d[0], d[1]);

    for (int i = 0; i < g[v].size(); i++)
    {
        int to = g[v][i].first;
        LL d = g[v][i].second;
        if (to == p)
            continue;
        LL newdist = dist;

        if (dp[to][0] + d == dp[v][0])
            newdist = max(newdist, dp[v][1]);
        else
            newdist = max(newdist, dp[v][0]);

        newdist += d;
        dfs2(to, v, newdist);
        ans[v] = min(ans[v], ans[to]);
    }
}

int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
    LL ANS = 0;
    n = N;
    x = L;
    while (M--)
    {
        g[A[M]].PB(MP(B[M], T[M]));
        g[B[M]].PB(MP(A[M], T[M]));
    }
    vector<LL> res;
    for (int i = 0; i < n; i++)
    {
        if (used[i])
            continue;
        color++;
        dfs(i);
        ANS = max(ANS, mx[i]);
        dfs2(i, -1, 0);
        //cout << ans[i] << " !\n";
        res.PB(ans[i]);
    }
    sort(all(res));
    reverse(all(res));
    assert(res.size() > 1);
    if (res.size() > 1)
    {
        LL best = mod * mod;
        // for (int i = 0; i < n; i++)
        //     for (int j = 0; j < n; j++)
        //         if (used[i] != used[j])
        //             best = min(lng[i] + lng[j] + x, best);
        // ANS = max(ANS, best);
        ANS = max(x + res[0] + res[1], ANS);
        // if (res.size() > 2)
        //     ANS = max(ANS, res[1] + res[2] + x + x);
    }
    return ANS;
}

#ifdef death

int main()
{
    int N, M, L, A[102], B[102], D[102];
    cin >> N >> M >> L;
    for (int i = 0; i < M; i++)
        cin >> A[i] >> B[i] >> D[i];
    cout << travelTime(N, M, L, A, B, D) << endl;
    return 0;
}

#endif

/*


7 5 1
0 1 5
1 2 3
2 3 2
1 4 4
4 5 2

8 6 100
0 1 10
1 2 15
2 7 11
3 4 3
4 5 332
5 6 3

12 8 2 
0 8 4
8 2 2
2 7 4
5 11 3
5 1 7
1 3 1
1 9 5
10 6 3

*/

Compilation message

dreaming.cpp: In function 'void dfs(int)':
dreaming.cpp:42:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < g[v].size(); i++)
                     ~~^~~~~~~~~~~~~
dreaming.cpp: In function 'void dfs2(int, int, long long int)':
dreaming.cpp:69:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < g[v].size(); i++)
                     ~~^~~~~~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:115:12: warning: unused variable 'best' [-Wunused-variable]
         LL best = mod * mod;
            ^~~~

Subtask #1
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 135 ms 25820 KB Output is correct
2 Correct 142 ms 25356 KB Output is correct
3 Correct 90 ms 21744 KB Output is correct
4 Correct 21 ms 8056 KB Output is correct
5 Correct 19 ms 6904 KB Output is correct
6 Correct 33 ms 9720 KB Output is correct
7 Correct 6 ms 5116 KB Output is correct
8 Correct 63 ms 13944 KB Output is correct
9 Correct 96 ms 18352 KB Output is correct
10 Correct 7 ms 5244 KB Output is correct
11 Correct 125 ms 19708 KB Output is correct
12 Correct 141 ms 22904 KB Output is correct
13 Correct 7 ms 5332 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 135 ms 25820 KB Output is correct
2 Correct 142 ms 25356 KB Output is correct
3 Correct 90 ms 21744 KB Output is correct
4 Correct 21 ms 8056 KB Output is correct
5 Correct 19 ms 6904 KB Output is correct
6 Correct 33 ms 9720 KB Output is correct
7 Correct 6 ms 5116 KB Output is correct
8 Correct 63 ms 13944 KB Output is correct
9 Correct 96 ms 18352 KB Output is correct
10 Correct 7 ms 5244 KB Output is correct
11 Correct 125 ms 19708 KB Output is correct
12 Correct 141 ms 22904 KB Output is correct
13 Correct 7 ms 5332 KB Output is correct
14 Correct 6 ms 5112 KB Output is correct
15 Correct 6 ms 4984 KB Output is correct
16 Correct 6 ms 5128 KB Output is correct
17 Correct 6 ms 5112 KB Output is correct
18 Correct 6 ms 5112 KB Output is correct
19 Correct 6 ms 5112 KB Output is correct
20 Correct 6 ms 5112 KB Output is correct
21 Correct 6 ms 5112 KB Output is correct
22 Incorrect 6 ms 5112 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 135 ms 25820 KB Output is correct
2 Correct 142 ms 25356 KB Output is correct
3 Correct 90 ms 21744 KB Output is correct
4 Correct 21 ms 8056 KB Output is correct
5 Correct 19 ms 6904 KB Output is correct
6 Correct 33 ms 9720 KB Output is correct
7 Correct 6 ms 5116 KB Output is correct
8 Correct 63 ms 13944 KB Output is correct
9 Correct 96 ms 18352 KB Output is correct
10 Correct 7 ms 5244 KB Output is correct
11 Correct 125 ms 19708 KB Output is correct
12 Correct 141 ms 22904 KB Output is correct
13 Correct 7 ms 5332 KB Output is correct
14 Correct 6 ms 5112 KB Output is correct
15 Correct 6 ms 4984 KB Output is correct
16 Correct 6 ms 5128 KB Output is correct
17 Correct 6 ms 5112 KB Output is correct
18 Correct 6 ms 5112 KB Output is correct
19 Correct 6 ms 5112 KB Output is correct
20 Correct 6 ms 5112 KB Output is correct
21 Correct 6 ms 5112 KB Output is correct
22 Incorrect 6 ms 5112 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 78 ms 13896 KB Output is correct
2 Incorrect 74 ms 13908 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 135 ms 25820 KB Output is correct
2 Correct 142 ms 25356 KB Output is correct
3 Correct 90 ms 21744 KB Output is correct
4 Correct 21 ms 8056 KB Output is correct
5 Correct 19 ms 6904 KB Output is correct
6 Correct 33 ms 9720 KB Output is correct
7 Correct 6 ms 5116 KB Output is correct
8 Correct 63 ms 13944 KB Output is correct
9 Correct 96 ms 18352 KB Output is correct
10 Correct 7 ms 5244 KB Output is correct
11 Correct 125 ms 19708 KB Output is correct
12 Correct 141 ms 22904 KB Output is correct
13 Correct 7 ms 5332 KB Output is correct
14 Incorrect 7 ms 5112 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 135 ms 25820 KB Output is correct
2 Correct 142 ms 25356 KB Output is correct
3 Correct 90 ms 21744 KB Output is correct
4 Correct 21 ms 8056 KB Output is correct
5 Correct 19 ms 6904 KB Output is correct
6 Correct 33 ms 9720 KB Output is correct
7 Correct 6 ms 5116 KB Output is correct
8 Correct 63 ms 13944 KB Output is correct
9 Correct 96 ms 18352 KB Output is correct
10 Correct 7 ms 5244 KB Output is correct
11 Correct 125 ms 19708 KB Output is correct
12 Correct 141 ms 22904 KB Output is correct
13 Correct 7 ms 5332 KB Output is correct
14 Correct 6 ms 5112 KB Output is correct
15 Correct 6 ms 4984 KB Output is correct
16 Correct 6 ms 5128 KB Output is correct
17 Correct 6 ms 5112 KB Output is correct
18 Correct 6 ms 5112 KB Output is correct
19 Correct 6 ms 5112 KB Output is correct
20 Correct 6 ms 5112 KB Output is correct
21 Correct 6 ms 5112 KB Output is correct
22 Incorrect 6 ms 5112 KB Output isn't correct
23 Halted 0 ms 0 KB -