Submission #962133

#	Time	Username	Problem	Language	Result	Execution time	Memory
962133		stev2005	Dreaming (IOI13_dreaming)	C++17	0 / 100	1041 ms	8536 KiB

dreaming

#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;
}

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: 0 / 14
• Subtask 2: 0 / 10
• Subtask 3: 0 / 23
• Subtask 4: 0 / 18
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23