Submission #962287

#	Time	Username	Problem	Language	Result	Execution time	Memory
962287		stev2005	Dreaming (IOI13_dreaming)	C++17	100 / 100	287 ms	15896 KiB

dreaming

#include "dreaming.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn = (1<<17), inf = (1<<30);
int n, m, lprice;

struct edge{
    int ver, cost;
    edge(){
        ver = -1;
        cost = 0;
    }
    edge(int _ver, int _cost){
        ver = _ver;
        cost = _cost;
    }
    bool operator<(const edge &other) const{
        return cost > other.cost;
    }
};

struct diamgr{
    int s, f;
    int cost, sum1, sum2;
    diamgr(){
        /*mid =*/ s = f = -1;
        cost = sum1 = sum2 = -1;
    }
    diamgr(int _s, int _f, int _cost, int _sum1, int _sum2){
        s = _s;
        f = _f;
        //mid = _mid;
        cost = _cost;
        sum1 = _sum1;
        sum2 = _sum2;
    }
};

vector <edge> v[maxn];
//bool used[maxn];
bool checkver[maxn];
int parsum[maxn], parsum1[maxn], parsum2[maxn];

int anscost;
int d[maxn];
int par[maxn], costpar[maxn];


inline void init_vectors(int *a, int *b, int *t){
    for (int i = 0; i < m; ++i){
        v[a[i]].push_back(edge(b[i], t[i]));
        v[b[i]].push_back(edge(a[i], t[i]));
        //cerr << a[i] << " " << b[i] << " " << t[i] << endl;
    }
}

void check_component(int ver){
    checkver[ver] = 1;
    for (auto nb: v[ver]){
        //cerr << "ver: " << ver << " nb: " << nb.ver << "\n";
        if (!checkver[nb.ver])
            check_component(nb.ver);
    }
}

/*int Dijkstra(int beg){
    memset(used, 0, sizeof(used));
    memset(par, -1, sizeof(par));
    memset(costpar, 0, sizeof(costpar));
    used[beg] = 1;
    checkver[beg] = 1;
    for (int i = 0; i < n; ++i)
        d[i] = inf;
    d[beg] = 0;
    costpar[beg] = 0;
    par[beg] = -1;
    priority_queue<edge> q;
    q.push(edge(beg, 0));
    int lastpopped = -1;
    while (!q.empty()){
        edge cur = q.top();
        q.pop();
        lastpopped = cur.ver;
        if (cur.cost <= d[cur.ver]){
            used[cur.ver] = 1;
            checkver[cur.ver] = 1;
            for (int i = 0; i < (int)v[cur.ver].size(); ++i){
                edge nb = v[cur.ver][i];
                if (cur.cost + nb.cost < d[nb.ver]){
                    par[nb.ver] = cur.ver;
                    costpar[nb.ver] = nb.cost;
                    d[nb.ver] = cur.cost + nb.cost;
                    nb.cost = d[nb.ver];
                    q.push(nb);
                }
            }
        }
    }
    return lastpopped;
}*/

int BFS(int beg){
    //cerr << "in the bfs(): " << beg << "\n";
    unordered_set<int> used;
    used.insert(beg);
    checkver[beg] = 1;
    costpar[beg] = 0;
    par[beg] = -1;
    d[beg] = 0;
    queue<int> q;
    int maxd = 0;
    int maxver = beg;
    q.push(beg);
    //cerr << "exactly before while\n";
    while(!q.empty()){
        int ver = q.front();
        //cerr << "in while ver: " << ver << "\n";
        q.pop();
        for (int i = 0; i < (int)v[ver].size(); ++i){
            edge nb = v[ver][i];
            if (used.find(nb.ver) == used.end()){
                d[nb.ver] = d[ver] + nb.cost;
                //cerr << "nb.ver: " << nb.ver << " d[nb.ver] == " << d[nb.ver] << endl;
                if (d[nb.ver] > maxd){
                    maxd = d[nb.ver];
                    maxver = nb.ver;
                }
                costpar[nb.ver] = nb.cost;
                par[nb.ver] = ver;
                used.insert(nb.ver);
                checkver[nb.ver] = 1;
                q.push(nb.ver);
            }
        }
    }
    //cerr << "after while, maxver: " << maxver << endl;
    return maxver;
}

int init_parsums(int s, int f, int *parsum){
    int cur = f, prev = -1;
    int cnt = 1;
    while (cur != -1){
        parsum[cnt] = parsum[cnt - 1] + costpar[cur];
        cur = par[cur];
        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};
}

pair<int, int> find_gr_dim(int ver){
    //cerr << "find_gr_dim ver: " << ver << " " << v[ver].size()<< "\n";
    //check_component(ver);
    if (v[ver].size() == 0){
        return {0, 0};
    }
    int s = BFS(ver);
    int f = BFS(s);
    //cerr << "Gr. diam: " << d[f] << endl;
    memset(parsum, 0, sizeof(parsum));
    int cntver = init_parsums(s, f, parsum);
    pair<int, int> sums = find_mindif(cntver, parsum);
    //cerr << "sums: " << sums.first << " " << sums.second << "\n";
    return sums;
}

inline void subtask123(int *a, int *b, int *t){
    init_vectors(a, b, t);
    pair<int, int> info1, info2;
    bool lamp = false;
    for (int i = 0; i < n; ++i){
        //cerr << "checkver[" << i << "] == " << checkver[i] << endl;
        if (!checkver[i]){
            if (!lamp){
                info1 = find_gr_dim(i);
                lamp = true;
            }
            else info2 = find_gr_dim(i);
        }
    }
    int diam1 = info1.first + info1.second;
    int diam2 = info2.first + info2.second;
    int max1 = max(info1.first, info1.second);
    int max2 = max (info2.first, info2.second);
    anscost = max1 + max2 + lprice;
    anscost = max(anscost, diam1);
    anscost = max(anscost, diam2);
}

inline void solve(int *a, int *b, int *t){
    init_vectors(a, b, t);
    pair<int, int> info;
    multiset<int> comp;
    for (int i = 0; i < n; ++i){
        //cerr << "checkver[" << i << "] == " << checkver[i] << endl;
        if (!checkver[i]){
            info = find_gr_dim(i);
            int m1 = max(info.first, info.second);
            int m2 = min(info.first, info.second);
            comp.insert(m1);
            int sum = m1 + m2;
            anscost = max(anscost, sum);
        }
    }
    int m1, m2, m3;
    m1 = m2 = m3 = 0;
    auto it = comp.end();
    --it;
    m1 = *it;
    if (it == comp.begin())
        return;
    --it;
    m2 = *it;
    if (it == comp.begin()){
        int sum = m1 + m2 + lprice;
        anscost = max(anscost, sum);
        return;
    }
    --it;
    m3 = *it;
    int sum = m1 + m2 + lprice;
    anscost = max(anscost, sum);
    sum = m2 + m3 + lprice + lprice;
    anscost = max(anscost, sum);

}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    n = N;
    m = M;
    lprice = L;
    //subtask1(A, B, T);
    //subtask123(A, B, T);
    solve(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";*/

/*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){
    init_vectors(a, b, t);
    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);
}
*/

Compilation message (stderr)

dreaming.cpp: In function 'int init_parsums(int, int, int*)':
dreaming.cpp:141:18: warning: unused variable 'prev' [-Wunused-variable]
  141 |     int cur = f, prev = -1;
      |                  ^~~~

• Subtask 1: 14 / 14
• Subtask 2: 10 / 10
• Subtask 3: 23 / 23
• Subtask 4: 18 / 18
• Subtask 5: 12 / 12
• Subtask 6: 23 / 23