oj.uz

Submission #962144

# Submission time Handle Problem Language Result Execution time Memory
962144 2024-04-13T07:37:48 Z stev2005 Dreaming (IOI13_dreaming) C++17
14 / 100
 1000 ms 8536 KB 
#include "dreaming.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn = (1<<17);
int n, m, lprice;
vector<pair<int, int> > v[maxn];
bool used[maxn];
int parsum1[maxn], parsum2[maxn];
int anscost;

int find_deepest(int ver){
    //cout << "ver " << ver << "\n";
    used[ver] = true;
    if (!used[v[ver][0].first])
        return find_deepest(v[ver][0].first);
    if (v[ver].size() > 1 && !used[v[ver][1].first])
        return find_deepest(v[ver][1].first);
    return ver;
}

inline void init_chain(int i, int &s, int &f){
    //cout << "i: " << i << "\n";
    used[i] = true;
    if (v[i].size() == 0) s = i;
    else s = find_deepest(v[i][0].first);
    //cerr << "found one end\n";
    if (v[i].size() <= 1) f = i;
    else f = find_deepest(v[i][1].first);
    //cerr << "found another end\n\n";
}

inline void find_chains(int &s1, int &f1, int &s2, int &f2){
    s1 = f1 = s2 = f2 = -1;
    for (int i = 0; i < n; ++i)
        if (!used[i]){
            if (s1 == -1) init_chain(i, s1, f1);
            else init_chain(i, s2, f2);
        }
}

int init_parsums(int s, int f, int *parsum){
    int cur = s, prev = -1;
    int cnt = 1;
    while (cur != f){
        for (pair<int, int> nb: v[cur])
            if (nb.first != prev){
                parsum[cnt] = parsum[cnt - 1] + nb.second;
                prev = cur;
                cur = nb.first;
                break;
            }
        cnt++;
    }
    return cnt;
}

pair<int, int> find_mindif(int n, int *parsum){
    if (n == 1) return {0, 0};
    if (n == 2) return {0, parsum[1]};
    int sum1 = -(1<<30) + 10, sum2 = (1<<30) - 10;
    for (int i = 0; i < n; ++i){
        int cursum1 = parsum[i];
        int cursum2 = parsum[n - 1] - parsum[i];
        if (abs(cursum2 - cursum1) < abs(sum2 - sum1)){
            sum1 = cursum1;
            sum2 = cursum2;
        }
    }
    return {sum1, sum2};
}

inline void subtask1(int *a, int *b, int *t){
    for (int i = 0; i < m; ++i){
        v[a[i]].push_back({b[i], t[i]});
        v[b[i]].push_back({a[i], t[i]});
        //cerr << a[i] << " " << b[i] << " " << t[i] << endl;
    }
    int s1, f1, s2, f2;
    find_chains(s1, f1, s2, f2);
    int n1 = init_parsums(s1, f1, parsum1);
    int n2 = init_parsums(s2, f2, parsum2);
    pair<int, int> sums1, sums2;
    sums1 = find_mindif(n1, parsum1);
    sums2 = find_mindif(n2, parsum2);
    //cout << sums1.first << " " << sums1.second << " " << sums2.first << " " << sums2.second << "\n";
    int max1 = max(sums1.first, sums1.second);
    int max2 = max(sums2.first, sums2.second);
    anscost = max1 + max2 + lprice;
    anscost = max(anscost, sums1.first + sums1.second);
    anscost = max(anscost, sums2.first + sums2.second);
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    n = N;
    m = M;
    lprice = L;
    subtask1(A, B, T);
    return anscost;
}

    /*cout << n1 << " " << n2 << "\n";
    for (int i = 0; i < n1; ++i)
        cout << parsum1[i] << " ";
    cout << "\n";
    for (int i = 0; i < n2; ++i)
        cout << parsum2[i] << " ";
    cout << "\n";*/

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 8532 KB Output is correct
2 Correct 29 ms 8536 KB Output is correct
3 Correct 19 ms 7516 KB Output is correct
4 Correct 5 ms 5980 KB Output is correct
5 Correct 5 ms 5980 KB Output is correct
6 Correct 9 ms 6236 KB Output is correct
7 Correct 2 ms 5468 KB Output is correct
8 Correct 15 ms 7068 KB Output is correct
9 Correct 18 ms 7260 KB Output is correct
10 Correct 2 ms 5468 KB Output is correct
11 Correct 38 ms 7800 KB Output is correct
12 Correct 27 ms 8280 KB Output is correct
13 Correct 2 ms 5468 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1042 ms 5468 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 8532 KB Output is correct
2 Correct 29 ms 8536 KB Output is correct
3 Correct 19 ms 7516 KB Output is correct
4 Correct 5 ms 5980 KB Output is correct
5 Correct 5 ms 5980 KB Output is correct
6 Correct 9 ms 6236 KB Output is correct
7 Correct 2 ms 5468 KB Output is correct
8 Correct 15 ms 7068 KB Output is correct
9 Correct 18 ms 7260 KB Output is correct
10 Correct 2 ms 5468 KB Output is correct
11 Correct 38 ms 7800 KB Output is correct
12 Correct 27 ms 8280 KB Output is correct
13 Correct 2 ms 5468 KB Output is correct
14 Execution timed out 1042 ms 5468 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

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

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1042 ms 5468 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 8532 KB Output is correct
2 Correct 29 ms 8536 KB Output is correct
3 Correct 19 ms 7516 KB Output is correct
4 Correct 5 ms 5980 KB Output is correct
5 Correct 5 ms 5980 KB Output is correct
6 Correct 9 ms 6236 KB Output is correct
7 Correct 2 ms 5468 KB Output is correct
8 Correct 15 ms 7068 KB Output is correct
9 Correct 18 ms 7260 KB Output is correct
10 Correct 2 ms 5468 KB Output is correct
11 Correct 38 ms 7800 KB Output is correct
12 Correct 27 ms 8280 KB Output is correct
13 Correct 2 ms 5468 KB Output is correct
14 Execution timed out 1042 ms 5468 KB Time limit exceeded
15 Halted 0 ms 0 KB -