Submission #134900

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
134900	2019-07-23 11:53:06	Bodo171	Valley (BOI19_valley)	C++14	100 / 100	599 ms	43640 KiB

valley

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
const int nmax=100005;
const long long inf=1LL*1e15;
vector< pair<int,int> > v[nmax];
vector<int> label[nmax];
long long lev[nmax],closest[nmax];
long long mn[20][nmax];
long long ans;
int tt[20][nmax];
int l[nmax],r[nmax],dpth[nmax],actual[nmax];
int nr,n,spec,q,root,i,x,y,z,j,blocat,nod,cat;
void dfs(int x)
{
    int nod=0;
    l[x]=++nr;
    for(int i=0;i<v[x].size();i++)
        if(!l[v[x][i].first])
    {
        nod=v[x][i].first;
        tt[0][nod]=x;dpth[nod]=dpth[x]+1;
        actual[label[x][i]]=nod;
        lev[nod]=1LL*lev[x]+v[x][i].second;
        dfs(nod);
        closest[x]=min(closest[x],closest[nod]+v[x][i].second);
    }
    r[x]=nr;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

valley.cpp: In function 'void dfs(int)':
valley.cpp:19:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<v[x].size();i++)
                 ~^~~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 27 / 27
• Subtask 3: 23 / 23
• Subtask 4: 41 / 41