Submission #412752

#	Time	Username	Problem	Language	Result	Execution time	Memory
412752		losmi247	꿈 (IOI13_dreaming)	C++14	0 / 100	57 ms	13892 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]; }



    if(m == n-1) return 0;

    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());

    vector <int> v;
    int maxi = 0,koji = -1;
    for(int i = 0; i < minmaxds.size()-1; i++){
        v.push_back(l+minmaxds.back()+minmaxds[i]);
        if(minmaxds[i] > maxi){
            maxi = minmaxds[i];
            koji = i;
        }
    }
    for(int i = 0; i < minmaxds.size()-1; i++){
        if(i == koji) continue;
        v.push_back(2*l+maxi+minmaxds[i]);
    }
    sort(v.begin(),v.end());

    return v.back();
}

Compilation message (stderr)

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:66: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]
   66 |         for(int j = 0; j < g[i].size(); j++){
      |                        ~~^~~~~~~~~~~~~
dreaming.cpp:72: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]
   72 |             if(j < g[i].size()-1) suf[j] = max(suf[j],suf[j+1]);
      |                ~~^~~~~~~~~~~~~~~
dreaming.cpp:74: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]
   74 |         for(int j = 0; j < g[i].size(); j++){
      |                        ~~^~~~~~~~~~~~~
dreaming.cpp:79: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]
   79 |             if(j < g[i].size()-1) ost = max(ost,suf[j+1]);
      |                ~~^~~~~~~~~~~~~~~
dreaming.cpp:98:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |     for(int i = 0; i < minmaxds.size()-1; i++){
      |                    ~~^~~~~~~~~~~~~~~~~~~
dreaming.cpp:105:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |     for(int i = 0; i < minmaxds.size()-1; i++){
      |                    ~~^~~~~~~~~~~~~~~~~~~

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