Submission #342753

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
342753	2021-01-02 17:42:04	nickmet2004	Hard route (IZhO17_road)	C++11	100 / 100	933 ms	145012 KiB

road

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>
#define F first
#define S second
#define int long long
using namespace std;
typedef pair<int , int> ipair;
const int N = 5e5 + 5;
int n;
vector<int> adj[N];
vector<ipair> D[N];
ipair dpD[N] , dpU[N];
int mx , cnt;
void dfsD(int u = 1 , int p = 0){
    for(int v : adj[u]){
        if(v==p)continue;
        dfsD(v , u);
        if(dpD[v].F + 1 > dpD[u].F) dpD[u] = dpD[v] , dpD[u].F++;
        else if(dpD[v].F + 1 == dpD[u].F) dpD[u].S += dpD[v].S;
    }
    if(adj[u].size() == 1 && u != 1) dpD[u].S = 1;
    for(int v : adj[u]) if(v != p)D[u].emplace_back(dpD[v].F + 1, dpD[v].S);
}
void dfsU(int u = 1, int p = 0){
    pair<int , int > d1 , d2;
    d1.F = d1.S = d2.F= d2.S = 0;
    d1 = dpD[u];
    ///d1.F--;
    //cout << d1.F << " " << d1.S << " kaaa " << endl;
    for(int v : adj[u]){
        if(v==p || d1.F == dpD[v].F + 1)continue;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

road.cpp: In function 'void solve()':
road.cpp:67:30: 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]
   67 |             for(int x = 0; x < D[u].size(); ++x) if(D[u][x].F ==x1)Y += D[u][x].S;
      |                            ~~^~~~~~~~~~~~~
road.cpp:68:30: 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]
   68 |             for(int x = 0; x < D[u].size(); ++x){
      |                            ~~^~~~~~~~~~~~~
road.cpp:75:30: 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]
   75 |             for(int x = 0; x < D[u].size(); ++x) if(D[u][x].F == x3)Y += D[u][x].S;
      |                            ~~^~~~~~~~~~~~~
road.cpp:80: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]
   80 |             for(int x = 0; x< D[u].size(); ++x)if(D[u][x].F == x2) Y += D[u][x].S;
      |                            ~^~~~~~~~~~~~~
road.cpp:81: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]
   81 |             for(int x= 0; x < D[u].size(); ++x){
      |                           ~~^~~~~~~~~~~~~
road.cpp:86:25: 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]
   86 |         for(int x = 0;x < D[u].size(); ++x)if(D[u][x].F == x3)Y+= D[u][x].S;
      |                       ~~^~~~~~~~~~~~~
road.cpp: At global scope:
road.cpp:91:8: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   91 |  main (){
      |        ^

• Subtask 1: 19 / 19
• Subtask 2: 33 / 33
• Subtask 3: 48 / 48