oj.uz

Submission #964155

# Submission time Handle Problem Language Result Execution time Memory
964155 2024-04-16T11:29:21 Z Amr Dreaming (IOI13_dreaming) C++17
32 / 100
 51 ms 24212 KB 
#include "dreaming.h"

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define S second
#define F first
#define all(x) (x).begin(),(x).end()
#define sz size()
#define Yes cout << "YES" << endl
#define No cout << "NO" << endl
#define pb(x) push_back(x);
#define endl '\n'
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
const int N=3e5+7;
ll INF=INT_MAX,mod=1e9+7;
int TT=1;
ll power(ll x, unsigned int y)
{
    ll res = 1;
    x = x; // % mod;
    if (x == 0) return 0;
    while (y > 0)
    {
        if (y & 1) res = (res*x)  ; // % mod;
        y = y>>1;
        x = (x*x) ; // % mod;
    }
    return res;
}
ll curans = -1e18;
ll inf = 1e18;
ll vis[N];
pair<ll,ll> dp[N];
ll ans[N];
ll mn = 1e18;
vector<pair<ll,ll> > v[N];
void dfs(ll x, ll par)
{
    if(vis[x]) return;
    vis[x] = 1;
    dp[x] = {0,-inf};
    vector<ll> vv;
    for(int i = 0; i < v[x].sz; i++)
    {
        ll newn = v[x][i].F;
        if(newn==par) continue;
        dfs(newn,x);
        vv.push_back(dp[newn].F+v[x][i].S);
    }
    sort(all(vv)); reverse(all(vv));
    if(vv.sz)  dp[x].F = vv[0];
    if(vv.sz>1)dp[x].S = vv[1];
}
void dfs2(ll x, ll par, ll w)
{
    if(vis[x]) return;
    vis[x] = 1;
    ans[x] = 0;
    if(par!=-1)
    {
        ll wh = dp[par].F;
        if(dp[x].F+w==wh) wh = dp[par].S;
        ans[x] = w+max(wh,ans[par]);

         mn = min(mn,max(dp[x].F,ans[x]));
    }
    else
    {
        curans = max(curans,dp[x].F+dp[x].S);
        mn = min(mn,dp[x].F);
    }
    for(int i = 0; i < v[x].sz; i++)
    {
        ll newn = v[x][i].F;
        if(newn==par) continue;
        dfs2(newn,x,v[x][i].S);
    }

}
int travelTime(int N,int M,int L, int A[],int B[],int T[])
{
    for(int i = 0; i < M; i++)
    {
        ll x = A[i], y = B[i], z = T[i];
        v[x].push_back({y,z});
        v[y].push_back({x,z});
    }
    for(int i = 0; i < N; i++)
    {
        if(!vis[i]) dfs(i,-1);
    }
    //for(int i = 0; i < N; i++) cout << dp[i].F << " " << dp[i].S << endl; cout << endl;
    for(int i =0; i < N; i++) vis[i] = 0;
    vector<ll> curv;
    for(int i = 0; i < N; i++)
    {
        if(!vis[i])
        {
            mn = 1e18;
            dfs2(i,-1,0);
            curv.push_back(mn);
            //cout << i << " " << mn << endl;
        }
    }


    sort(all(curv)); reverse(all(curv));
    if(curv.sz==1) return max(curans,curv[0]);
    if(curv.sz==2) return max(curans,curv[0] + curv[1] + L);
    else
    {
        ll best = 1e18;
        best = min(best,max(curv[0]+curv[1]+L,curv[1]+curv[2]+2*L));
        best = min(best,max(curv[1]+curv[0]+L,curv[0]+curv[2]+2*L));
        return max(best,curans);
    }
}

Compilation message

dreaming.cpp: In function 'void dfs(ll, ll)':
dreaming.cpp:45:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for(int i = 0; i < v[x].sz; i++)
      |                      ^
dreaming.cpp: In function 'void dfs2(ll, ll, ll)':
dreaming.cpp:74:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |     for(int i = 0; i < v[x].sz; i++)
      |                      ^

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 24212 KB Output is correct
2 Correct 41 ms 23636 KB Output is correct
3 Correct 27 ms 22616 KB Output is correct
4 Correct 8 ms 12380 KB Output is correct
5 Correct 7 ms 11612 KB Output is correct
6 Correct 12 ms 13400 KB Output is correct
7 Correct 3 ms 10588 KB Output is correct
8 Correct 20 ms 17672 KB Output is correct
9 Correct 27 ms 20752 KB Output is correct
10 Correct 2 ms 10588 KB Output is correct
11 Correct 37 ms 21116 KB Output is correct
12 Correct 51 ms 22860 KB Output is correct
13 Correct 2 ms 10588 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 24212 KB Output is correct
2 Correct 41 ms 23636 KB Output is correct
3 Correct 27 ms 22616 KB Output is correct
4 Correct 8 ms 12380 KB Output is correct
5 Correct 7 ms 11612 KB Output is correct
6 Correct 12 ms 13400 KB Output is correct
7 Correct 3 ms 10588 KB Output is correct
8 Correct 20 ms 17672 KB Output is correct
9 Correct 27 ms 20752 KB Output is correct
10 Correct 2 ms 10588 KB Output is correct
11 Correct 37 ms 21116 KB Output is correct
12 Correct 51 ms 22860 KB Output is correct
13 Correct 2 ms 10588 KB Output is correct
14 Correct 2 ms 10584 KB Output is correct
15 Correct 2 ms 10588 KB Output is correct
16 Correct 2 ms 10584 KB Output is correct
17 Correct 2 ms 10588 KB Output is correct
18 Correct 2 ms 10588 KB Output is correct
19 Correct 2 ms 10588 KB Output is correct
20 Correct 2 ms 10588 KB Output is correct
21 Correct 2 ms 10744 KB Output is correct
22 Incorrect 2 ms 10588 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 16096 KB Output is correct
2 Correct 18 ms 16092 KB Output is correct
3 Correct 27 ms 16200 KB Output is correct
4 Correct 19 ms 16092 KB Output is correct
5 Correct 18 ms 16004 KB Output is correct
6 Correct 20 ms 16856 KB Output is correct
7 Correct 19 ms 16352 KB Output is correct
8 Correct 19 ms 16096 KB Output is correct
9 Correct 23 ms 16084 KB Output is correct
10 Correct 18 ms 16092 KB Output is correct
11 Correct 2 ms 10588 KB Output is correct
12 Correct 8 ms 14700 KB Output is correct
13 Correct 6 ms 14548 KB Output is correct
14 Correct 5 ms 14548 KB Output is correct
15 Correct 5 ms 14548 KB Output is correct
16 Correct 5 ms 14548 KB Output is correct
17 Correct 5 ms 14548 KB Output is correct
18 Correct 5 ms 14548 KB Output is correct
19 Correct 6 ms 14548 KB Output is correct
20 Correct 2 ms 10588 KB Output is correct
21 Correct 2 ms 10704 KB Output is correct
22 Correct 2 ms 10588 KB Output is correct
23 Correct 5 ms 14548 KB Output is correct

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 24212 KB Output is correct
2 Correct 41 ms 23636 KB Output is correct
3 Correct 27 ms 22616 KB Output is correct
4 Correct 8 ms 12380 KB Output is correct
5 Correct 7 ms 11612 KB Output is correct
6 Correct 12 ms 13400 KB Output is correct
7 Correct 3 ms 10588 KB Output is correct
8 Correct 20 ms 17672 KB Output is correct
9 Correct 27 ms 20752 KB Output is correct
10 Correct 2 ms 10588 KB Output is correct
11 Correct 37 ms 21116 KB Output is correct
12 Correct 51 ms 22860 KB Output is correct
13 Correct 2 ms 10588 KB Output is correct
14 Correct 2 ms 10584 KB Output is correct
15 Correct 2 ms 10588 KB Output is correct
16 Correct 2 ms 10584 KB Output is correct
17 Correct 2 ms 10588 KB Output is correct
18 Correct 2 ms 10588 KB Output is correct
19 Correct 2 ms 10588 KB Output is correct
20 Correct 2 ms 10588 KB Output is correct
21 Correct 2 ms 10744 KB Output is correct
22 Incorrect 2 ms 10588 KB Output isn't correct
23 Halted 0 ms 0 KB -