Submission #962164

#	Time	Username	Problem	Language	Result	Execution time	Memory
962164		serkanrashid	Dreaming (IOI13_dreaming)	C++14	47 / 100	62 ms	20404 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5+5;

struct edge
{
    long long ver,dist;
    edge(){};
    edge(int vi, long long di)
    {
        ver = vi;
        dist = di;
    }
};

struct Point
{
    int x,y,d;
    Point(){};
    Point(int xi, int yi, int di)
    {
        x = xi;
        y = yi;
        d = di;
    }
};

int n;

vector<edge> g[MAXN];
long long sub[MAXN],used[MAXN];

long long mind,vut;
vector<long long> comp;

void clear_used()
{
    for(int i = 0; i < n; i++) used[i] = 0;
}

void clear_g()
{
    for(int i = 0; i < n; i++) g[i].clear();
}

void dfs_dp(int beg, long long gor)
{
    used[beg] = 1;
    long long maxch = max(sub[beg],gor);
    vut = max(vut,maxch);
    mind = min(mind,maxch);
    long long fir = 0, sec = 0;
    for(edge nb : g[beg])
    {
        if(!used[nb.ver])
        {
            if(nb.dist+sub[nb.ver] >= fir)
            {
                sec = fir;
                fir = nb.dist+sub[nb.ver];
            }
            else if(nb.dist+sub[nb.ver] >= sec)
            {
                sec = nb.dist+sub[nb.ver];
            }
        }
    }
    for(edge nb : g[beg])
    {
        if(!used[nb.ver])
        {
            long long new_gor = gor;
            if(nb.dist+sub[nb.ver] == fir) new_gor = max(new_gor,sec);
            else new_gor = max(new_gor,fir);
            new_gor += nb.dist;
            dfs_dp(nb.ver,new_gor);
        }
    }
}

void dfs(int beg)
{
    used[beg] = 1;
    for(edge nb : g[beg])
    {
        if(!used[nb.ver])
        {
            dfs(nb.ver);
            sub[beg] = max(sub[beg],sub[nb.ver]+nb.dist);
        }
    }
}

Point sp[MAXN];
int idx,lead[MAXN],br[MAXN];

bool cmp(Point p1, Point p2)
{
    return p1.d<p2.d;
}

int find_lead(int x)
{
    if(lead[x]==x) return x;
    return lead[x] = find_lead(lead[x]);
}

void union1(int x, int y)
{
    if(br[x]<br[y])
    {
        br[y] += br[x];
        lead[x] = y;
    }
    else
    {
        br[x] += br[y];
        lead[y] = x;
    }
}

int travelTime(int N,int M,int L,int A[],int B[],int T[])
{
    n = N;
    for(int i = 0; i < M; i++)
    {
        g[A[i]].push_back({B[i],T[i]});
        g[B[i]].push_back({A[i],T[i]});
    }
    for(int i = 0; i < N; i++) if(!used[i]) dfs(i);
    clear_used();
    for(int i = 0; i < N; i++)
    {
        if(!used[i])
        {
            mind = 1e9+5;
            dfs_dp(i,0);
            comp.push_back(mind);
        }
    }
    idx = 0;
    for(int i = 0; i < comp.size(); i++)
    {
        for(int j = i+1; j < comp.size(); j++)
        {
            sp[idx] = {i,j,comp[i]+comp[j]+L};
            idx++;
        }
    }
    clear_used();
    clear_g();
    for(int i = 0; i < comp.size(); i++)
    {
        lead[i] = i;
        br[i] = 1;
    }
    sort(sp,sp+idx,cmp);
    for(int i = 0; i < idx; i++)
    {
        int x = sp[i].x;
        int y = sp[i].y;
        x = find_lead(x);
        y = find_lead(y);
        if(x != y)
        {
            g[sp[i].x].push_back({sp[i].y,sp[i].d});
            g[sp[i].y].push_back({sp[i].x,sp[i].d});
            union1(x,y);
        }
    }


    ///
    memset(sub,0,sizeof(sub));
    for(int i = 0; i < comp.size(); i++) if(!used[i]) dfs(i);
    clear_used();
    long long ans = 0;
    for(int i = 0; i < comp.size(); i++)
    {
        if(!used[i])
        {
            mind = 1e9+5;
            dfs_dp(i,0);
            ans = max(ans,mind);
        }
    }
    return max(ans,vut);
}

Compilation message (stderr)

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:145:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  145 |     for(int i = 0; i < comp.size(); i++)
      |                    ~~^~~~~~~~~~~~~
dreaming.cpp:147:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  147 |         for(int j = i+1; j < comp.size(); j++)
      |                          ~~^~~~~~~~~~~~~
dreaming.cpp:149:43: warning: narrowing conversion of '((comp.std::vector<long long int>::operator[](((std::vector<long long int>::size_type)i)) + comp.std::vector<long long int>::operator[](((std::vector<long long int>::size_type)j))) + ((__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type)L))' from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'int' [-Wnarrowing]
  149 |             sp[idx] = {i,j,comp[i]+comp[j]+L};
dreaming.cpp:155:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  155 |     for(int i = 0; i < comp.size(); i++)
      |                    ~~^~~~~~~~~~~~~
dreaming.cpp:178:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  178 |     for(int i = 0; i < comp.size(); i++) if(!used[i]) dfs(i);
      |                    ~~^~~~~~~~~~~~~
dreaming.cpp:181:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  181 |     for(int i = 0; i < comp.size(); i++)
      |                    ~~^~~~~~~~~~~~~

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