Submission #412750

#	Time	Username	Problem	Language	Result	Execution time	Memory
412750		losmi247	Dreaming (IOI13_dreaming)	C++14	0 / 100	55 ms	15056 KiB

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
typedef long long ll;
const int N = 1e5+23;

int n,m,l;
int a[N],b[N],t[N];
vector <pair<int,int>> g[N];
int rut[N],parent[N],komp[N];
int dep[N],mxdepdole[N];
int maxd[N];


vector <int> sad;
void dfs(int x,int par){
    sad.push_back(x);
    parent[x] = par;
    mxdepdole[x] = dep[x];
    for(auto f : g[x]){
        int u = f.first;
        if(u == par) continue;
        komp[u] = komp[x];

        dep[u] = dep[x]+f.second;
        dfs(u,x);
        mxdepdole[x] = max(mxdepdole[x],mxdepdole[u]);
    }
}

void dfs1(int x,int par,int ostali){
    maxd[x] = max(dep[x]+ostali,mxdepdole[x]-dep[x]);
    for(auto f : g[x]){
        int u = f.first;
        if(u == par) continue;
        dfs1(u,x,ostali);
    }
}

int travelTime(int br1,int br2,int br3,int *jed,int *dva,int *tri){
    n = br1;
    m = br2;
    l = br3;
    for(int i = 0; i < m; i++){ a[i+1] = jed[i]+1; b[i+1] = dva[i]+1; t[i+1] = tri[i]; }


    for(int i = 1; i <= m; i++){
        g[a[i]].push_back({b[i],t[i]});
        g[b[i]].push_back({a[i],t[i]});
    }
    int cnt = 1;
    vector <int> minmaxds;
    for(int i = 1; i <= n; i++){
        if(komp[i]) continue;

        komp[i] = cnt;
        rut[cnt] = i;
        sad.clear();
        dfs(i,0);


        vector <int> pref(g[i].size(),0),suf(g[i].size(),0);
        for(int j = 0; j < g[i].size(); j++){
            pref[j] = g[i][j].second+mxdepdole[g[i][j].first];
            if(j > 0) pref[j] = max(pref[j],pref[j-1]);
        }
        for(int j = g[i].size()-1; j >= 0; j--){
            suf[j] = g[i][j].second+mxdepdole[g[i][j].first];
            if(j < g[i].size()-1) suf[j] = max(suf[j],suf[j+1]);
        }
        for(int j = 0; j < g[i].size(); j++){
            int u = g[i][j].first;

            int ost = 0;
            if(j > 0) ost = max(ost,pref[j-1]);
            if(j < g[i].size()-1) ost = max(ost,suf[j+1]);

            dfs1(u,i,ost);
        }
        maxd[i] = mxdepdole[i];

        int minmaxd = 2e9;
        for(auto f : sad) minmaxd = min(minmaxd,maxd[f]);
        minmaxds.push_back(minmaxd);

        cnt++;
    }
    cnt--;
    assert(cnt == n-m);

    sort(minmaxds.begin(),minmaxds.end());

    int br = 0;
    for(auto f : minmaxds){
        if(f == minmaxds.back()) br++;
    }

    if(br >= 3){
        return 2*l+2*minmaxds.back();
    }
    if(br == 2){
        return l+2*minmaxds.back();
    }
    assert(br == 1);

    int drugi = 0;
    for(auto f : minmaxds){
        if(f != minmaxds.back()) drugi = f;
    }

    if(drugi){
        return l+minmaxds.back()+drugi;
    }
    return 0; /// samo jedna komponenta
}

Compilation message (stderr)

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:63:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |         for(int j = 0; j < g[i].size(); j++){
      |                        ~~^~~~~~~~~~~~~
dreaming.cpp:69:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |             if(j < g[i].size()-1) suf[j] = max(suf[j],suf[j+1]);
      |                ~~^~~~~~~~~~~~~~~
dreaming.cpp:71:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |         for(int j = 0; j < g[i].size(); j++){
      |                        ~~^~~~~~~~~~~~~
dreaming.cpp:76:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |             if(j < g[i].size()-1) ost = max(ost,suf[j+1]);
      |                ~~^~~~~~~~~~~~~~~

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