oj.uz

Submission #520819

# Submission time Handle Problem Language Result Execution time Memory
520819 2022-01-31T05:19:01 Z noob_c0de Dreaming (IOI13_dreaming) C++17
18 / 100
 43 ms 12800 KB 
#include<bits/stdc++.h>
#include "dreaming.h"
using namespace std;
// #define int long long
#define ar array
#define db double
#define sz(x) (int)x.size()
const db pi = acos(-1);
const int mxn = 1e5 + 7;
int in[mxn], out[mxn];
int vis[mxn];
vector<ar<int, 2> > g[mxn];
int tmp, node;
int d(int u)
{
    return in[u] + out[u];
}
int leaf(int u)
{
    return max(in[u], out[u]);
}
void dfs(int u)
{
    vis[u] = 1;
    for (auto [v, w] : g[u])
    {
        if (vis[v]) continue;
        dfs(v);
        in[u] = max(in[u], in[v] + w);
    }
}
void dfs2(int u, int p)
{
    int mx1 = 0, mx2 = 0;
    for (auto [v, w] : g[u])
    {
        if (v == p) continue;
        if (in[v] + w > mx1) mx2 = mx1, mx1 = in[v] + w;
        else mx2 = max(mx2, in[v] + w);
    }
    for (auto [v, w] : g[u])
    {
        if (v == p) continue;
        if (in[v] + w == mx1) out[v] = max(out[u], mx2) + w;
        else out[v] = max(out[u], mx1) + w;
        dfs2(v, u);
    }
    if (tmp > leaf(u))
    {
        tmp = leaf(u);
        node = u;
    }
}   
int travelTime(int n, int m, int l, int a[], int b[], int t[])
{
    for (int i = 0; i < m; i++)
    {
        g[a[i] + 1].push_back({b[i] + 1, t[i]});
        g[b[i] + 1].push_back({a[i] + 1, t[i]});
    }
    vector<int> ans;
    int mx = 0;
    for (int i = 1; i <= n; i++)
    if (!vis[i]) 
    {
        tmp = mxn;
        dfs(i);
        dfs2(i, i);
        ans.push_back(node);
        mx = max(mx, d(node));
        // cout << i - 1 << ' ' << tmp << '\n';
    }
    sort(ans.begin(), ans.end(), [](int u, int v)
    {
        return leaf(u) > leaf(v);
    });
    if (sz(ans) >= 2) mx = max(mx, leaf(ans[0]) + leaf(ans[1]) + l);
    if (sz(ans) >= 3) mx = max(mx, leaf(ans[1]) + leaf(ans[2]) + 2 * l);
    return mx;
};
// int n, m, l;
// int a[mxn], b[mxn], t[mxn];
// signed main()
// {
//     ios::sync_with_stdio(0);
//     cin.tie(0); cout.tie(0);
//     // De nghi ko bat ultra instinct tay nhanh hon nao luc lam bai
//     cin >> n >> m >> l;
//     for (int i = 0; i < m; i++) 
//     {
//         cin >> a[i] >> b[i] >> t[i];
//     }
//     cout << travelTime(n, m, l, a, b, t);
//     /*
//     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*/
//     return 0;
// }

Subtask #1
0 / 14.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 1 ms 2636 KB Output is correct
3 Correct 1 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 2 ms 2652 KB Output is correct
7 Correct 2 ms 2636 KB Output is correct
8 Correct 2 ms 2656 KB Output is correct
9 Correct 2 ms 2652 KB Output is correct
10 Incorrect 2 ms 2636 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

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

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 6844 KB Output is correct
2 Correct 20 ms 6836 KB Output is correct
3 Correct 19 ms 6756 KB Output is correct
4 Correct 18 ms 6860 KB Output is correct
5 Correct 19 ms 6840 KB Output is correct
6 Correct 20 ms 7276 KB Output is correct
7 Correct 20 ms 7028 KB Output is correct
8 Correct 18 ms 6736 KB Output is correct
9 Correct 19 ms 6720 KB Output is correct
10 Correct 20 ms 6976 KB Output is correct
11 Correct 2 ms 2656 KB Output is correct
12 Correct 8 ms 4296 KB Output is correct
13 Correct 6 ms 4296 KB Output is correct
14 Correct 6 ms 4188 KB Output is correct
15 Correct 5 ms 4296 KB Output is correct
16 Correct 5 ms 4168 KB Output is correct
17 Correct 5 ms 3784 KB Output is correct
18 Correct 6 ms 4296 KB Output is correct
19 Correct 5 ms 4168 KB Output is correct
20 Correct 2 ms 2656 KB Output is correct
21 Correct 3 ms 2660 KB Output is correct
22 Correct 2 ms 2636 KB Output is correct
23 Correct 5 ms 4168 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 1 ms 2636 KB Output is correct
3 Correct 1 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 2 ms 2652 KB Output is correct
7 Correct 2 ms 2636 KB Output is correct
8 Correct 2 ms 2656 KB Output is correct
9 Correct 2 ms 2652 KB Output is correct
10 Incorrect 2 ms 2636 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

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