Submission #962113

#	Time	Username	Problem	Language	Result	Execution time	Memory
962113		n3rm1n	Dreaming (IOI13_dreaming)	C++17	10 / 100	1056 ms	15344 KiB

dreaming

#include<bits/stdc++.h>
#include "dreaming.h"
using namespace std;
const long long MAXN = 1e5 + 10;
vector < pair < long long, long long > > g[MAXN];
long long mark[MAXN];
long long used[MAXN];
void dfs0(long long beg)
{
    mark[beg] = 1;
    used[beg] = 1;
    long long nb;
    for (long long i = 0; i < g[beg].size(); ++ i)
    {
        nb = g[beg][i].first;
        if(!used[nb])
            dfs0(nb);
    }
}
long long maxdist = 0;
long long dfs(long long beg)
{
    used[beg] = 1;
    long long nb, distt;
    long long maxx = 0;
    for (long long 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;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
    for (long long 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]));
    }
    long long n = N;
    dfs0(0);
    long long marked1 = 0, marked0 = 0;
    long long mindist1 = 1e17, mindist2 = 1e17;
    long long currmax;
    long long index1 = 0, index2 = 0;
    for (long long i = 0; i < n; ++ i)
    {
        if(mark[i])
        {
            memset(used, 0 ,sizeof(used));

            currmax = dfs(i);
            if(currmax < mindist1)
            {
                mindist1 = currmax;
                index1 = i;
            }
        }
        else
        {
            memset(used, 0 ,sizeof(used));

            currmax = dfs(i);
            if(currmax < mindist2)
            {
                mindist2 = currmax;
                index2 = i;
            }
        }

    }
    g[index1].push_back(make_pair(index2, L));
    g[index2].push_back(make_pair(index1, L));
    long long ans = 0;
    for (long long i = 0; i < n; ++ i)
    {
        memset(used, 0, sizeof(used));
        ans = max(ans, dfs(i));
    }
    return ans;
}

Compilation message (stderr)

dreaming.cpp: In function 'void dfs0(long long int)':
dreaming.cpp:13:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |     for (long long i = 0; i < g[beg].size(); ++ i)
      |                           ~~^~~~~~~~~~~~~~~
dreaming.cpp: In function 'long long int dfs(long long int)':
dreaming.cpp:26:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     for (long long i = 0; i < g[beg].size(); ++ i)
      |                           ~~^~~~~~~~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:43:15: warning: unused variable 'marked1' [-Wunused-variable]
   43 |     long long marked1 = 0, marked0 = 0;
      |               ^~~~~~~
dreaming.cpp:43:28: warning: unused variable 'marked0' [-Wunused-variable]
   43 |     long long marked1 = 0, marked0 = 0;
      |                            ^~~~~~~

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