oj.uz

Submission #422857

# Submission time Handle Problem Language Result Execution time Memory
422857 2021-06-10T13:08:58 Z Trickster Dreaming (IOI13_dreaming) C++14
18 / 100
 82 ms 16720 KB 
//Suleyman Atayew

#include "dreaming.h"
#include <algorithm>
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <vector>
#include <bitset>
#include <queue>
#include <cmath>
#include <map>
#include <set>
 
#define maxN 200010
#define ff first
#define ss second
#define pb push_back
#define ll long long
#define mod 1000000007
#define pii pair <int, int>
#define sz(a) (int)(a.size())
ll bigmod(ll a, ll b) { if(b==0)return 1; ll ret = bigmod(a, b/2); return ret * ret % mod * (b%2 ? a : 1) % mod; }

using namespace std;

int n, m, l, mn, mx;
int vis[maxN];
pii F[maxN][5];
vector <pii> E[maxN];

void dfs(int nd, int pr)
{
    vis[nd] = 1;

    for(auto i: E[nd]) {
        int to = i.ff;
        int yol = i.ss;

        if(to != pr) {
            dfs(to, nd);

            if(F[nd][0].ff < F[to][0].ff + yol) {
                F[nd][1] = F[nd][0];
                F[nd][0] = {F[to][0].ff + yol, F[to][0].ss};
            } else if(F[nd][1].ff < F[to][0].ff + yol)
                F[nd][1] = {F[to][0].ff + yol, F[to][0].ss};
        }
    }
}

void dfs2(int nd, int pr, int yol)
{
    if(pr) {
        if(F[nd][0].ss != F[pr][0].ss) {
	        if(F[nd][0].ff < F[pr][0].ff + yol) {
	            F[nd][1] = F[nd][0];
	            F[nd][0] = {F[pr][0].ff + yol, F[pr][0].ss};
	        } 
	        else if(F[nd][1].ff < F[pr][0].ff + yol)
	            F[nd][1] = {F[pr][0].ff + yol, F[pr][0].ss};
    	} else {
			if(F[nd][0].ff < F[pr][1].ff + yol) {
	            F[nd][1] = F[nd][0];
	            F[nd][0] = {F[pr][1].ff + yol, F[pr][1].ss};
	        } 
	        else if(F[nd][1].ff < F[pr][1].ff + yol)
	            F[nd][1] = {F[pr][1].ff + yol, F[pr][1].ss};
    	}
    }

    mn = min(mn, F[nd][0].ff);
    mx = max(mx, F[nd][0].ff + F[nd][1].ff);

    for(auto i: E[nd])
        if(i.ff != pr)
            dfs2(i.ff, nd, i.ss);
}


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++) {
        E[A[i]+1].pb({B[i]+1, T[i]});
        E[B[i]+1].pb({A[i]+1, T[i]});
    }

    vector <int> v;
    for(int i = 1; i <= n; i++) {
        if(vis[i]) continue;

        mn = 1e9+7;
        dfs(i, 0);
        dfs2(i, 0, 0);

        mn = (mn == 1e9+7 ? 0 : mn);

        v.pb(mn);
    }

    sort(v.begin(), v.end());
    reverse(v.begin(), v.end());

    return max(max(mx, (v.size() >= 2 ? v[0]+v[1]+L : 0)), (v.size() >= 3 ? v[1]+v[2]+2*L : 0));
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 16720 KB Output is correct
2 Correct 82 ms 16424 KB Output is correct
3 Correct 40 ms 14148 KB Output is correct
4 Correct 10 ms 6732 KB Output is correct
5 Correct 9 ms 6092 KB Output is correct
6 Correct 15 ms 7500 KB Output is correct
7 Incorrect 3 ms 4940 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 16720 KB Output is correct
2 Correct 82 ms 16424 KB Output is correct
3 Correct 40 ms 14148 KB Output is correct
4 Correct 10 ms 6732 KB Output is correct
5 Correct 9 ms 6092 KB Output is correct
6 Correct 15 ms 7500 KB Output is correct
7 Incorrect 3 ms 4940 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 11736 KB Output is correct
2 Correct 35 ms 11736 KB Output is correct
3 Correct 33 ms 11712 KB Output is correct
4 Correct 31 ms 11756 KB Output is correct
5 Correct 32 ms 11652 KB Output is correct
6 Correct 32 ms 12360 KB Output is correct
7 Correct 47 ms 11976 KB Output is correct
8 Correct 32 ms 11708 KB Output is correct
9 Correct 30 ms 11604 KB Output is correct
10 Correct 41 ms 11968 KB Output is correct
11 Correct 4 ms 4940 KB Output is correct
12 Correct 9 ms 7624 KB Output is correct
13 Correct 10 ms 8644 KB Output is correct
14 Correct 9 ms 7564 KB Output is correct
15 Correct 9 ms 7752 KB Output is correct
16 Correct 8 ms 7240 KB Output is correct
17 Correct 8 ms 6216 KB Output is correct
18 Correct 9 ms 8904 KB Output is correct
19 Correct 10 ms 7240 KB Output is correct
20 Correct 4 ms 4940 KB Output is correct
21 Correct 4 ms 4940 KB Output is correct
22 Correct 4 ms 5068 KB Output is correct
23 Correct 9 ms 7368 KB Output is correct

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 16720 KB Output is correct
2 Correct 82 ms 16424 KB Output is correct
3 Correct 40 ms 14148 KB Output is correct
4 Correct 10 ms 6732 KB Output is correct
5 Correct 9 ms 6092 KB Output is correct
6 Correct 15 ms 7500 KB Output is correct
7 Incorrect 3 ms 4940 KB Output isn't correct
8 Halted 0 ms 0 KB -