Submission #636961

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
636961	2022-08-30T18:50:59 Z	PagodePaiva	Dreaming (IOI13_dreaming)	C++14	Compilation error	0 ms	0 KB

dreaming

#include<bits/stdc++.h>
#include<dreaming.h>
#define int long long
#define ms(v) memset(v, -1, sizeof v)
#define pb push_back
#define mp make_pair
#define sz size
#define ll long long int
#define pi pair <int,int>
#define itn int
#define fr first
#define sc second
#define srt(v) sort(v.begin(), v.end())
#define rvs(v) reverse(v.begin(), v.end())
#define mod 1000000007
#define INF 1e18
#define N 100010
using namespace std;

int n, m, l;
vector <pi> g[N];
int dist[N]; 
int dista[N];
int distu[N], distv[N];
int distr[N];
vector <int> centros;
int res = -1;

bool comp(int a, int b){
    if(dist[a] > dist[b]) return true;
    if(dist[a] < dist[b]) return false;
    return a > b;
}

void dfs(int node, int pai){
    for(auto v : g[node]){
        if(v.fr == pai) continue;
        dista[v.fr] = dista[node] + v.sc;
        dfs(v.fr, node);
    }

    return;
}

void dfsu(int node, int pai){
    for(auto v : g[node]){
        if(v.fr == pai) continue;
        distu[v.fr] = distu[node] + v.sc;
        dfsu(v.fr, node);
    }

    return;
}

void dfsv(int node, int pai){
    for(auto v : g[node]){
        if(v.fr == pai) continue;
        distv[v.fr] = distv[node] + v.sc;
        dfsu(v.fr, node);
    }

    return;
}

void build(int x){
    if(dist[x] != -1) return;

    ms(dista);
    dista[x] = 0;
    dfs(x, -1);

    int u = x;

    for(int i = 1;i <= n;i++){
        if(dista[u] < dista[i]) u = i;
    }

    ms(dista);
    dfs(u, -1);

    int v = u;
    for(int i = 1;i <= n;i++){
        if(dista[v] < dista[i]) v = i;
    }

    ms(distu);
    ms(distv);
    dfsu(u, -1);
    dfsv(v, -1);
    int cent = 1;

    for(int i = 1;i <= n;i++){
        dist[i] = max(dist[i], max(distu[i], distv[i]));
        if(dist[cent] > dist[i]) cent = i;
    }

    centros.pb(cent);

    return;
}

int solve(){
    ms(distr);
    distr[1] = 0;
    dfs(x, -1);

    int u = x;

    for(int i = 1;i <= n;i++){
        if(distr[u] < distr[i]) u = i;
    }

    ms(distr);
    dfs(u, -1);

    int v = u;
    for(int i = 1;i <= n;i++){
        if(distr[v] < distr[i]) v = i;
    }

    ms(distu);
    ms(distv);
    dfsu(u, -1);
    dfsv(v, -1);
    int cent = 1;

    int resp = -1;
    for(int i = 1;i <= n;i++){
        resp = max(resp, max(distu[i], distv[i]));
    }

    return resp;
}

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

    ms(dist);

    for(int i = 1;i <= n;i++){
        if(dist[i] == -1){
            build(i);
        }
    }

    sort(centros.begin(), centros.end(), comp);

    for(int i = 1;i < centros.size();i++){
        g[centros[0]].pb({g[centros[i]], l});
        g[centros[i]].pb({g[centros[0]], l});
    }

    res = solve();

    return res;
}

Compilation message

dreaming.cpp: In function 'long long int solve()':
dreaming.cpp:105:9: error: 'x' was not declared in this scope
  105 |     dfs(x, -1);
      |         ^
dreaming.cpp:125:9: warning: unused variable 'cent' [-Wunused-variable]
  125 |     int cent = 1;
      |         ^~~~
dreaming.cpp: At global scope:
dreaming.cpp:17:11: error: expected ',' or '...' before numeric constant
   17 | #define N 100010
      |           ^~~~~~
dreaming.cpp:135:20: note: in expansion of macro 'N'
  135 | int travelTime(int N, int M, int L, int A[], int B[], int T[]){
      |                    ^
dreaming.cpp: In function 'long long int travelTime(long long int)':
dreaming.cpp:137:9: error: 'M' was not declared in this scope
  137 |     m = M;
      |         ^
dreaming.cpp:138:9: error: 'L' was not declared in this scope
  138 |     l = L;
      |         ^
dreaming.cpp:140:11: error: 'B' was not declared in this scope
  140 |         g[B[i]].pb({A[i], T[i]});
      |           ^
dreaming.cpp:140:21: error: 'A' was not declared in this scope
  140 |         g[B[i]].pb({A[i], T[i]});
      |                     ^
dreaming.cpp:140:27: error: 'T' was not declared in this scope
  140 |         g[B[i]].pb({A[i], T[i]});
      |                           ^
dreaming.cpp:154:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  154 |     for(int i = 1;i < centros.size();i++){
      |                   ~~^~~~~~~~~~~~~~~~
dreaming.cpp:155:44: error: no matching function for call to 'std::vector<std::pair<long long int, long long int> >::push_back(<brace-enclosed initializer list>)'
  155 |         g[centros[0]].pb({g[centros[i]], l});
      |                                            ^
In file included from /usr/include/c++/10/vector:67,
                 from /usr/include/c++/10/queue:61,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:86,
                 from dreaming.cpp:1:
/usr/include/c++/10/bits/stl_vector.h:1187:7: note: candidate: 'void std::vector<_Tp, _Alloc>::push_back(const value_type&) [with _Tp = std::pair<long long int, long long int>; _Alloc = std::allocator<std::pair<long long int, long long int> >; std::vector<_Tp, _Alloc>::value_type = std::pair<long long int, long long int>]'
 1187 |       push_back(const value_type& __x)
      |       ^~~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:1187:35: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const value_type&' {aka 'const std::pair<long long int, long long int>&'}
 1187 |       push_back(const value_type& __x)
      |                 ~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_vector.h:1203:7: note: candidate: 'void std::vector<_Tp, _Alloc>::push_back(std::vector<_Tp, _Alloc>::value_type&&) [with _Tp = std::pair<long long int, long long int>; _Alloc = std::allocator<std::pair<long long int, long long int> >; std::vector<_Tp, _Alloc>::value_type = std::pair<long long int, long long int>]'
 1203 |       push_back(value_type&& __x)
      |       ^~~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:1203:30: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::vector<std::pair<long long int, long long int> >::value_type&&' {aka 'std::pair<long long int, long long int>&&'}
 1203 |       push_back(value_type&& __x)
      |                 ~~~~~~~~~~~~~^~~
dreaming.cpp:156:44: error: no matching function for call to 'std::vector<std::pair<long long int, long long int> >::push_back(<brace-enclosed initializer list>)'
  156 |         g[centros[i]].pb({g[centros[0]], l});
      |                                            ^
In file included from /usr/include/c++/10/vector:67,
                 from /usr/include/c++/10/queue:61,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:86,
                 from dreaming.cpp:1:
/usr/include/c++/10/bits/stl_vector.h:1187:7: note: candidate: 'void std::vector<_Tp, _Alloc>::push_back(const value_type&) [with _Tp = std::pair<long long int, long long int>; _Alloc = std::allocator<std::pair<long long int, long long int> >; std::vector<_Tp, _Alloc>::value_type = std::pair<long long int, long long int>]'
 1187 |       push_back(const value_type& __x)
      |       ^~~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:1187:35: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const value_type&' {aka 'const std::pair<long long int, long long int>&'}
 1187 |       push_back(const value_type& __x)
      |                 ~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_vector.h:1203:7: note: candidate: 'void std::vector<_Tp, _Alloc>::push_back(std::vector<_Tp, _Alloc>::value_type&&) [with _Tp = std::pair<long long int, long long int>; _Alloc = std::allocator<std::pair<long long int, long long int> >; std::vector<_Tp, _Alloc>::value_type = std::pair<long long int, long long int>]'
 1203 |       push_back(value_type&& __x)
      |       ^~~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:1203:30: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::vector<std::pair<long long int, long long int> >::value_type&&' {aka 'std::pair<long long int, long long int>&&'}
 1203 |       push_back(value_type&& __x)
      |                 ~~~~~~~~~~~~~^~~