답안 #636962

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
636962	2022-08-30T19:05:16 Z	PagodePaiva	꿈 (IOI13_dreaming)	C++14	컴파일 오류	0 ms	0 KB

dreaming

#include<bits/stdc++.h>
#include<dreaming.h>
#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(1, -1);

    int u = 1;

    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 resp = -1;
    for(int i = 1;i <= n;i++){
        resp = max(resp, max(distu[i], distv[i]));
    }

    return resp;
}

int travelTime(int k, int M, int L, int A[], int B[], int T[]){
    n = k;
    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 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:152:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |     for(int i = 1;i < centros.size();i++){
      |                   ~~^~~~~~~~~~~~~~~~
dreaming.cpp:153:44: error: no matching function for call to 'std::vector<std::pair<int, int> >::push_back(<brace-enclosed initializer list>)'
  153 |         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<int, int>; _Alloc = std::allocator<std::pair<int, int> >; std::vector<_Tp, _Alloc>::value_type = std::pair<int, 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<int, 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<int, int>; _Alloc = std::allocator<std::pair<int, int> >; std::vector<_Tp, _Alloc>::value_type = std::pair<int, 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<int, int> >::value_type&&' {aka 'std::pair<int, int>&&'}
 1203 |       push_back(value_type&& __x)
      |                 ~~~~~~~~~~~~~^~~
dreaming.cpp:154:44: error: no matching function for call to 'std::vector<std::pair<int, int> >::push_back(<brace-enclosed initializer list>)'
  154 |         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<int, int>; _Alloc = std::allocator<std::pair<int, int> >; std::vector<_Tp, _Alloc>::value_type = std::pair<int, 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<int, 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<int, int>; _Alloc = std::allocator<std::pair<int, int> >; std::vector<_Tp, _Alloc>::value_type = std::pair<int, 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<int, int> >::value_type&&' {aka 'std::pair<int, int>&&'}
 1203 |       push_back(value_type&& __x)
      |                 ~~~~~~~~~~~~~^~~