oj.uz

Submission #1092629

# Submission time Handle Problem Language Result Execution time Memory
1092629 2024-09-24T15:54:11 Z TsotneSV Dreaming (IOI13_dreaming) C++17
0 / 100
 39 ms 18012 KB 
#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
/* /\_/\
  (= ._.)
  / >  \>
*/
//#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") // codeforces

// #define int long long
#define fi first
#define se second
#define pb push_back
#define ins insert
#define mp make_pair
#define send {ios_base::sync_with_stdio(false);}
#define help {cin.tie(0);}
#define endl '\n'
#define sz(x) ((long long) (x).size())
#define all(x) (x).begin(),(x).end()
#define print(x) cout<<(x)<<" ";
#define printl(x) cout<<(x)<<endl
#define dbg(x) cerr<<#x<<" "<<x<<endl

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vpi;
typedef vector<pll> vpl;


const int inf=2e9; 
const ll INF=1e18; 

int travelTime(int n, int m, int l, int A[], int B[], int T[])
{

    vector<pii> g[n];

    for(int i=0;i<m;i++) {
        g[A[i]].pb({B[i],T[i]});
        g[B[i]].pb({A[i],T[i]});
    }

    vector<bool> vis(n,0); vector<int> dp1(n),dp2(n),dp3(n),par(n),mn(n,inf);

    function<void(int,int,int)> dfs1 = [&](int v,int p,int we) -> void {

        vis[v] = 1; par[v] = (p == -1 ? v : par[p]);

        dp1[v] = dp2[v] = 0;

        for(auto [u,w] : g[v]) {
            if(u == p) continue;
            dfs1(u,v,w);
            if(dp1[u] + w > dp1[v]) {
                dp2[v] = dp1[v];
                dp1[v] = dp1[u] + w;
            }else if(dp1[u] + w > dp2[v]) dp2[v] = dp1[u] + w;
        }

    };

    function<void(int,int,int)> dfs2 = [&](int v,int p,int we) -> void {

        if(p != -1) dp3[v] = max(dp3[p],(dp1[p] == dp1[v] + we ? dp2[p] : dp1[p])) + we;
        else dp3[v] = 0;

        for(auto [u,w] : g[v]) {
            if(u == p) continue;
            dfs2(u,v,w);
        }

    };  

    int ans = 0;

    for(int i=0;i<n;i++) {
        if(!vis[i]) {
            dfs1(i,-1,0);
            dfs2(i,-1,0);
        } ans = max(ans,dp1[i] + dp3[i]);
    }

    for(int i=0;i<n;i++) mn[par[i]] = min(mn[par[i]],max(dp1[i],dp3[i]));
    
    vi v;

    for(int i=0;i<n;i++) {
        if(mn[i] != inf) {
            v.pb(mn[i]);
        }
    } sort(all(v));

    if(v.size() <= 2) {
        int sum = l*sz(v); 
        for(int i : v) sum += i;
        ans = max(ans,sum);
    }else {
        int k = sz(v);
        ans = max({ans,v[k-1] + l + v[k-2],v[k-2] + 2*l + v[k-3]});
    }

    return ans;
}

/*int main() {

    int A[] = {0,8,2,5,5,1,1,10},B[] = {8,2,7,11,1,3,9,6},T[] = {4,2,4,3,7,1,5,3};

    printl(travelTime(12,8,2,A,B,T));

    return 0;

}*/

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 18012 KB Output is correct
2 Correct 39 ms 17492 KB Output is correct
3 Correct 29 ms 15440 KB Output is correct
4 Correct 6 ms 2908 KB Output is correct
5 Correct 5 ms 1884 KB Output is correct
6 Correct 12 ms 4188 KB Output is correct
7 Incorrect 1 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 18012 KB Output is correct
2 Correct 39 ms 17492 KB Output is correct
3 Correct 29 ms 15440 KB Output is correct
4 Correct 6 ms 2908 KB Output is correct
5 Correct 5 ms 1884 KB Output is correct
6 Correct 12 ms 4188 KB Output is correct
7 Incorrect 1 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 7504 KB Output is correct
2 Correct 19 ms 7640 KB Output is correct
3 Correct 23 ms 7516 KB Output is correct
4 Correct 19 ms 7544 KB Output is correct
5 Correct 21 ms 7516 KB Output is correct
6 Correct 26 ms 8200 KB Output is correct
7 Correct 21 ms 7900 KB Output is correct
8 Correct 19 ms 7388 KB Output is correct
9 Correct 18 ms 7380 KB Output is correct
10 Correct 21 ms 7772 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 9 ms 5332 KB Output is correct
13 Correct 8 ms 5344 KB Output is correct
14 Correct 8 ms 5344 KB Output is correct
15 Correct 8 ms 5448 KB Output is correct
16 Correct 9 ms 5344 KB Output is correct
17 Correct 10 ms 5344 KB Output is correct
18 Correct 8 ms 5344 KB Output is correct
19 Correct 9 ms 5344 KB Output is correct
20 Incorrect 0 ms 356 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 18012 KB Output is correct
2 Correct 39 ms 17492 KB Output is correct
3 Correct 29 ms 15440 KB Output is correct
4 Correct 6 ms 2908 KB Output is correct
5 Correct 5 ms 1884 KB Output is correct
6 Correct 12 ms 4188 KB Output is correct
7 Incorrect 1 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -