Submission #574510

#	Time	Username	Problem	Language	Result	Execution time	Memory
574510		Mounir	Dreaming (IOI13_dreaming)	C++14	100 / 100	220 ms	25296 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
#define pb push_back
#define all(x) x.begin(), x.end()
#define chmin(x, v) x = min(x, v)
#define chmax(x, v) x = max(x, v)
#define sz(x) (int)x.size()
#define pii pair<int, int>
#define int long long
using namespace std;

const int N = 3e5;

vector<pii> aretes[N];
bool vu[N][3];
int dists[N][3];
int nNoeuds, nAretes;

vector<int> cc;
void calcDist(int noeud, int distCur, int step){
    vu[noeud][step] = true;
    dists[noeud][step] = distCur;
    if (step == 0)
        cc.pb(noeud);

    for (pii arete : aretes[noeud]){
        if (vu[arete.first][step]) continue;
        calcDist(arete.first, distCur + arete.second, step);
    }
}

pii calcDiametre(int root){
    cc = {};
    calcDist(root, 0, 0);
 /*   cout << "cc " << root << endl;
    for (int noeud : cc)    
        cout << noeud << " ";
    cout << endl;*/
    int ext1 = -1;
    for (int noeud : cc){
        if (ext1 == - 1 || dists[noeud][0] > dists[ext1][0])
            ext1 = noeud;
    }
    calcDist(ext1, 0, 1);
    int ext2 = -1;
    for (int noeud : cc){
        if (ext2 == - 1 || dists[noeud][1] > dists[ext2][1])
            ext2 = noeud;
    }

    int mid = -1, res;
    calcDist(ext2, 0, 2);
    for (int noeud : cc){
        if (mid == -1 || max(dists[noeud][1], dists[noeud][2]) < res)
            mid = noeud, res = max(dists[noeud][1], dists[noeud][2]);
    }
/*
    for (int t = 1; t <= 2; ++t){
        for (int nod = 0; nod < nNoeuds; ++nod)
            cout << dists[nod][t] << " ";
        cout << endl;
    }

    cout << "----------" << endl;
    cout << "mid " <<  mid << endl;*/

    return {res, mid};
}

signed travelTime(signed n, signed m, signed POIDS, signed A[], signed B[], signed T[]) {
    nNoeuds = n; nAretes = m;
    for (int iArete = 0; iArete < nAretes; ++iArete){
        aretes[A[iArete]].pb({B[iArete], T[iArete]});
        aretes[B[iArete]].pb({A[iArete], T[iArete]});
    }

    vector<pii> roots;
    for (int noeud = 0; noeud < nNoeuds; ++noeud){
        if (vu[noeud][0]) continue;
 //       cout << "NOEUD " << noeud << endl;
        roots.pb(calcDiametre(noeud));
    }

    sort(all(roots));
    set<int> potentiels = {roots[0].second, roots[sz(roots) - 1].second};
    if (sz(roots) >= 2)
        potentiels.insert(roots[sz(roots) - 2].second);
    
    int minDiametre = 1e18;
    for (int milieu : potentiels){
        for (pii cc : roots){
            int root = cc.second;
            if (milieu != root){
                aretes[milieu].pb({root, POIDS});
                aretes[root].pb({milieu, POIDS});
            }
        }

        for (int noeud = 0; noeud < nNoeuds; ++noeud)
            for (int i = 0; i < 3; ++i)
                vu[noeud][i] = false;
        pii inutile = calcDiametre(milieu);
        int diametre = 0;
        for (int noeud = 0; noeud < nNoeuds; ++noeud)
            for (int i = 0; i < 3; ++i)
                chmax(diametre, dists[noeud][i]);
        chmin(minDiametre, diametre);
        for (pii cc : roots){
            int root = cc.second;
            if (milieu != root){
                aretes[milieu].pop_back();
                aretes[root].pop_back();
            }
        }
    }
    return (int)minDiametre;
}

Compilation message (stderr)

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:102:13: warning: variable 'inutile' set but not used [-Wunused-but-set-variable]
  102 |         pii inutile = calcDiametre(milieu);
      |             ^~~~~~~
dreaming.cpp: In function 'std::pair<long long int, long long int> calcDiametre(long long int)':
dreaming.cpp:67:21: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
   67 |     return {res, mid};
      |                     ^

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