Submission #173133

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
173133	2020-01-03 12:28:05	Akashi	Construction of Highway (JOI18_construction)	C++14	100 / 100	391 ms	107016 KiB

construction

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 <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n;
int a[N], H[N], TT[N], sz[N], Next[N], x[N], y[N];
bool viz[N];
vector <int> v[N];
deque <pair <int, int> > L[N];
vector <pair <int, int> > aux, tmp;
vector <int> val;
void adfs(int nod = 1){
    sz[nod] = 1;
    for(auto &it : v[nod]){
        TT[it] = nod; H[it] = H[nod] + 1;
        adfs(it);
        if(sz[it] > sz[v[nod][0]]) swap(it, v[nod][0]);
    }
}
void bdfs(int nod = 1){
    if(v[nod].empty()) return ;
    Next[v[nod][0]] = Next[nod];
    bdfs(v[nod][0]);
    for(int i = 1; i < v[nod].size() ; ++i){
        Next[v[nod][i]] = v[nod][i];
        bdfs(v[nod][i]);
    }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

construction.cpp: In function 'void bdfs(int)':
construction.cpp:27:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 1; i < v[nod].size() ; ++i){
                    ~~^~~~~~~~~~~~~~~
construction.cpp: In function 'int main()':
construction.cpp:125:39: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
         printf("%d\n", calc_path(x[i]));
                        ~~~~~~~~~~~~~~~^
construction.cpp:112:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
construction.cpp:113:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i = 1; i <= n ; ++i) scanf("%d", &a[i]);
                                  ~~~~~^~~~~~~~~~~~~
construction.cpp:116:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &x[i], &y[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 9 / 9
• Subtask 3: 84 / 84