Submission #962319

#	Time	Username	Problem	Language	Result	Execution time	Memory
962319		n3rm1n	Dreaming (IOI13_dreaming)	C++17	59 / 100	1074 ms	32708 KiB

dreaming

#include<bits/stdc++.h>
#include "dreaming.h"
using namespace std;
const int MAXN = 5e5 + 10;
vector < pair < int, int > > g[MAXN];
int mark[MAXN];
int used[MAXN];
void dfs0(int beg)
{
    mark[beg] = 1;
    used[beg] = 1;
    int nb;
    for (int i = 0; i < g[beg].size(); ++ i)
    {
        nb = g[beg][i].first;
        if(!used[nb])
            dfs0(nb);
    }
}
int far = 0, far_index = 0;
void dfs_diam(int beg, int to_there)
{
    if(far <= to_there)
    {
        far = to_there;
        far_index = beg;
    }
    used[beg] = 1;
    int nb, distt;
    for (int i = 0; i < g[beg].size(); ++ i)
    {
        nb = g[beg][i].first;
        distt = g[beg][i].second;
        if(!used[nb])dfs_diam(nb, to_there + distt);
    }
}
int maxdist = 0;
int dfs(int beg)
{
    used[beg] = 1;
    int nb, distt;
    int maxx = 0;
    for (int i = 0; i < g[beg].size(); ++ i)
    {
        nb = g[beg][i].first;
        distt = g[beg][i].second;
        if(!used[nb])maxx = max(maxx, dfs(nb)+distt);
    }
    return maxx;
}
vector < pair < int, int >  > path;
int st, fi;
int marked[MAXN];
int dfs_form(int beg, int add)
{
    marked[beg] = 1;
    used[beg] = 1;
    if(beg == fi)
    {
        path.push_back(make_pair(beg, add));
        return 1;
    }
    int nb, distt;
    int found = 0;
    for (int i = 0; i < g[beg].size(); ++ i)
    {
        nb = g[beg][i].first;
        distt = g[beg][i].second;
        if(!used[nb])
        {
            if(dfs_form(nb, add + distt))found = 1;
        }
    }
    if(found)path.push_back(make_pair(beg, add));
    return found;
}

int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
    for (int i = 0; i < M; ++ i)
    {
        g[A[i]].push_back(make_pair(B[i], T[i]));
        g[B[i]].push_back(make_pair(A[i], T[i]));
    }

    int n = N;

    priority_queue < pair < int/*diam*/, int > > pq;
    for (int i = 0; i < n; ++ i)
    {
        if(marked[i])continue;
        int aa1 = 0, bb1 = 0;
        int aa2 = 0, bb2 = 0;
        memset(used, 0, sizeof(used));
        far = 0;
        far_index = 0;
        dfs_diam(i, 0);
        aa1 = far_index;
        memset(used, 0, sizeof(used));
        far = 0;
        far_index = 0;
        dfs_diam(aa1, 0);
        bb1 = far_index;

        path.clear();
        st = aa1;
        fi = bb1;
        memset(used, 0, sizeof(used));
        dfs_form(st, 0);

        int index1 = path[0].first;
        int total1 = path[0].second;
        int best1 = total1, curr;
        for (int i = 1; i < path.size(); ++ i)
        {
            curr = max(path[i].second, total1 - path[i].second);
            if(curr < best1)
            {
                best1 = curr;
                index1 = path[i].first;
            }
        }

        pq.push(make_pair(best1, index1));
       // cout << "component " << best1 << "  " << index1 << endl;
    }


    int sz = pq.size();

    while(pq.size() > 1)
    {
        int diam1 = pq.top().first;
        int ii1 = pq.top().second;
        pq.pop();
        int diam2 = pq.top().first;
        int ii2 = pq.top().second;
        pq.pop();


        int neww = max(max(diam1, diam2), min(diam1, diam2) + L);
        g[ii1].push_back(make_pair(ii2, L));
        g[ii2].push_back(make_pair(ii1, L));
        if(diam1 > diam2)pq.push(make_pair(neww, ii1));
        else pq.push(make_pair(neww, ii2));

    }


        int aa1 = 0, bb1 = 0;
        int aa2 = 0, bb2 = 0;
        memset(used, 0, sizeof(used));
        far = 0;
        far_index = 0;
        dfs_diam(0, 0);
        aa1 = far_index;
        memset(used, 0, sizeof(used));
    return dfs(aa1);

    ///

}

Compilation message (stderr)

dreaming.cpp: In function 'void dfs0(int)':
dreaming.cpp:13:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |     for (int i = 0; i < g[beg].size(); ++ i)
      |                     ~~^~~~~~~~~~~~~~~
dreaming.cpp: In function 'void dfs_diam(int, int)':
dreaming.cpp:30:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for (int i = 0; i < g[beg].size(); ++ i)
      |                     ~~^~~~~~~~~~~~~~~
dreaming.cpp: In function 'int dfs(int)':
dreaming.cpp:43:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for (int i = 0; i < g[beg].size(); ++ i)
      |                     ~~^~~~~~~~~~~~~~~
dreaming.cpp: In function 'int dfs_form(int, int)':
dreaming.cpp:65:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     for (int i = 0; i < g[beg].size(); ++ i)
      |                     ~~^~~~~~~~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:114:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |         for (int i = 1; i < path.size(); ++ i)
      |                         ~~^~~~~~~~~~~~~
dreaming.cpp:93:13: warning: unused variable 'aa2' [-Wunused-variable]
   93 |         int aa2 = 0, bb2 = 0;
      |             ^~~
dreaming.cpp:93:22: warning: unused variable 'bb2' [-Wunused-variable]
   93 |         int aa2 = 0, bb2 = 0;
      |                      ^~~
dreaming.cpp:129:9: warning: unused variable 'sz' [-Wunused-variable]
  129 |     int sz = pq.size();
      |         ^~
dreaming.cpp:150:22: warning: unused variable 'bb1' [-Wunused-variable]
  150 |         int aa1 = 0, bb1 = 0;
      |                      ^~~
dreaming.cpp:151:13: warning: unused variable 'aa2' [-Wunused-variable]
  151 |         int aa2 = 0, bb2 = 0;
      |             ^~~
dreaming.cpp:151:22: warning: unused variable 'bb2' [-Wunused-variable]
  151 |         int aa2 = 0, bb2 = 0;
      |                      ^~~

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