oj.uz

Submission #575611

# Submission time Handle Problem Language Result Execution time Memory
575611 2022-06-11T06:49:28 Z Belgutei Dreaming (IOI13_dreaming) C++17
32 / 100
 73 ms 16640 KB 
#include "dreaming.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define ff first
#define ss second
#define pb push_back
#define mk make_pair
#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); 
#define MOD 1000000007
#define MOD1 1000000009
#define sqr(x) sqr((x)*(x))

void debug_out() { cerr << endl; }
template<typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << ' ' << H; debug_out(T...); }
#ifdef BE_DEBUG
#define debug(...) cerr << "\033[1;31m(" << #__VA_ARGS__ << "):\033[0m", debug_out(__VA_ARGS__)
#else
#define debug(...)
#endif

const int BB = 100005;

vector<pair<int,int> > edge[BB];
bool visited[BB];
vector<int> v;
int a[BB],b[BB]; // 
int tmp;
multiset<int> s;
multiset<int> :: iterator it;

vector<int> gold;
int mn;
int ans;

void dfs(int node) {
    //cout << node << ' ';
    visited[node] = 1;
    v.pb(node);
    int tmp_mx = 0;
    for(auto x: edge[node]) {
        if(visited[x.ff] == 1) continue;
        a[x.ff] = x.ss;
        dfs(x.ff);
        b[node] = max(b[node], a[x.ff]);
        if(node == tmp) {
            s.insert(-(b[x.ff] + x.ss));
        }
        ans = max(ans, tmp_mx + a[x.ff]);
        tmp_mx = max(tmp_mx,a[x.ff]);
    }
    a[node] += b[node];
}

void go(int node, int cost) {
    visited[node] = 1;
    if(s.size() != 0) {
        it = s.begin();
        mn = min(mn, max(b[node],cost - *it));
    }
    else {
        mn = min(mn, max(b[node], cost));
    }
    for(auto x: edge[node]) {
        if(visited[x.ff] == 1) continue;
        if(tmp == node) {
            it = s.lower_bound(-a[x.ff]);
            s.erase(it);
        }
        go(x.ff, x.ss + cost);
        s.insert(-a[x.ff]);
    }
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    for(int i = 0; i < M; i ++) {
        edge[A[i]].pb({B[i], T[i]});
        edge[B[i]].pb({A[i], T[i]});
    }
    for(int i = 0; i < N; i ++) {
        if(visited[i] == 1) continue;
        s.clear();
        v.clear();
        tmp = i;
        dfs(i);
        for(auto x: v) {
            visited[x] = 0;
        }
        mn = 1e9;
        go(i,0);
        gold.pb(mn);
    }
    /*
    for(int i = 0; i < N; i ++) {
        cout << a[i] << ' ';
    }
    cout << '\n';
    for(int i = 0; i < N; i ++) {
        cout << b[i] << ' ';
    }
    cout << '\n';
    */
    sort(gold.begin(), gold.end());
    
    if(gold.size() == 1) {
        return max(ans,gold[gold.size() - 1]);
    }
    int q = gold.size() - 1;
    if(gold.size() == 2) {
        return max(ans,gold[q] + gold[q - 1] + L);
    }
    return max(ans, max(gold[q] + gold[q - 1] + L, gold[q - 1] + gold[q - 2] + L + L));
    return 0;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 16640 KB Output is correct
2 Correct 63 ms 16348 KB Output is correct
3 Correct 44 ms 13580 KB Output is correct
4 Correct 10 ms 4692 KB Output is correct
5 Correct 6 ms 3668 KB Output is correct
6 Correct 14 ms 5716 KB Output is correct
7 Correct 1 ms 2644 KB Output is correct
8 Correct 27 ms 7836 KB Output is correct
9 Correct 36 ms 10920 KB Output is correct
10 Correct 2 ms 2772 KB Output is correct
11 Correct 51 ms 11780 KB Output is correct
12 Correct 73 ms 14156 KB Output is correct
13 Correct 2 ms 2772 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 16640 KB Output is correct
2 Correct 63 ms 16348 KB Output is correct
3 Correct 44 ms 13580 KB Output is correct
4 Correct 10 ms 4692 KB Output is correct
5 Correct 6 ms 3668 KB Output is correct
6 Correct 14 ms 5716 KB Output is correct
7 Correct 1 ms 2644 KB Output is correct
8 Correct 27 ms 7836 KB Output is correct
9 Correct 36 ms 10920 KB Output is correct
10 Correct 2 ms 2772 KB Output is correct
11 Correct 51 ms 11780 KB Output is correct
12 Correct 73 ms 14156 KB Output is correct
13 Correct 2 ms 2772 KB Output is correct
14 Correct 1 ms 2644 KB Output is correct
15 Correct 1 ms 2644 KB Output is correct
16 Incorrect 2 ms 2644 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 6080 KB Output is correct
2 Correct 26 ms 6180 KB Output is correct
3 Correct 24 ms 6136 KB Output is correct
4 Correct 21 ms 6168 KB Output is correct
5 Correct 24 ms 6136 KB Output is correct
6 Correct 23 ms 6616 KB Output is correct
7 Correct 21 ms 6232 KB Output is correct
8 Correct 25 ms 6108 KB Output is correct
9 Correct 19 ms 6096 KB Output is correct
10 Correct 26 ms 6248 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 6 ms 4048 KB Output is correct
13 Correct 6 ms 4048 KB Output is correct
14 Correct 6 ms 4048 KB Output is correct
15 Correct 5 ms 4048 KB Output is correct
16 Correct 5 ms 4048 KB Output is correct
17 Correct 5 ms 3792 KB Output is correct
18 Correct 6 ms 4048 KB Output is correct
19 Correct 5 ms 4048 KB Output is correct
20 Correct 2 ms 2644 KB Output is correct
21 Correct 1 ms 2644 KB Output is correct
22 Correct 2 ms 2644 KB Output is correct
23 Correct 5 ms 4048 KB Output is correct

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 16640 KB Output is correct
2 Correct 63 ms 16348 KB Output is correct
3 Correct 44 ms 13580 KB Output is correct
4 Correct 10 ms 4692 KB Output is correct
5 Correct 6 ms 3668 KB Output is correct
6 Correct 14 ms 5716 KB Output is correct
7 Correct 1 ms 2644 KB Output is correct
8 Correct 27 ms 7836 KB Output is correct
9 Correct 36 ms 10920 KB Output is correct
10 Correct 2 ms 2772 KB Output is correct
11 Correct 51 ms 11780 KB Output is correct
12 Correct 73 ms 14156 KB Output is correct
13 Correct 2 ms 2772 KB Output is correct
14 Correct 1 ms 2644 KB Output is correct
15 Correct 1 ms 2644 KB Output is correct
16 Incorrect 2 ms 2644 KB Output isn't correct
17 Halted 0 ms 0 KB -