답안 #843694

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
843694	2023-09-04T12:47:49 Z	nonono	꿈 (IOI13_dreaming)	C++14	컴파일 오류	0 ms	0 KB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;

const int mxN = 100005;

vector<vector<int>> adj(mxN);
int mark[mxN];
int high[mxN], _high[mxN];
vector<int> vertex;

void dfs(int u, int par) {
    vertex.push_back(u);
    mark[u] = 1;
    high[u] = 0;
    
    for(int v : adj[u]) {
        if(v == par) continue ;
        dfs(v, u);
        high[u] = max(high[u], high[v] + 1);
    }
}

void reroot(int u, int par) {
    vector<int> k;
    
    for(int v : adj[u]) {
        if(v == par) continue ;
        k.push_back(v);
    }
   
   for(int i = 0; i < k.size(); i ++) {
       int v = k[i];
       L.push_back(max((!L.empty() ? L.back() ? 0), high[v] + 1));
   }
   
   for(int i = 0; i < k.size(); i ++) {
       int v = k[k.size() - 1 - i];
       R.push_back(max((!R.empty() ? R.back() ? 0), high[v] + 1));
   }
   
   reverse(R.begin(), R.end());
   
   for(int i = 0; i < k.size(); i ++) {
       int v = k[i];
       if(v == par) continue ;
       
       _high[v] = max(_high[v], _high[u] + 1);
       if(i) _high[v] = max(_high[v], L[i - 1] + 1);
       if(i + 1 < R.size()) _high[v] = max(_high[v], R[i + 1] + 1);
       reroot(v, u);
   }
}

int travelTime(int N, int M, int L, vector<int> A, vector<int> B, vector<int> T) {
    
    for(int i = 0; i < M; i ++) {
        adj[A[i]].push_back({B[i], T[i]});
        adj[B[i]].push_back({A[i], T[i]});
    }
    
    vector<int> f;
    int ans = 0;
    
    for(int i = 0; i < N; i ++) {
        if(!mark[i]) {
            dfs(i, i);
            reroot(i, i);
            
            int timer = max(high[vertex.back()], _high[vertex.back()]);
            for(int x : vertex) {
                ans = max(ans, high[x] + _high[x]);
                timer = min(timer, max(high[x], _high[x]));
            }
            
            f.push_back(timer);
            vertex.clear();
        }
    }
    
    sort(f.begin(), f.end());
    if(f.size() > 1) {
        ans = max(ans, f[0] + f[1] + L);
    }
    
    return ans;
}

Compilation message

dreaming.cpp: In function 'void reroot(int, int)':
dreaming.cpp:32:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |    for(int i = 0; i < k.size(); i ++) {
      |                   ~~^~~~~~~~~~
dreaming.cpp:34:8: error: 'L' was not declared in this scope
   34 |        L.push_back(max((!L.empty() ? L.back() ? 0), high[v] + 1));
      |        ^
dreaming.cpp:34:50: error: expected ':' before ')' token
   34 |        L.push_back(max((!L.empty() ? L.back() ? 0), high[v] + 1));
      |                                                  ^
      |                                                  :
dreaming.cpp:34:50: error: expected primary-expression before ')' token
dreaming.cpp:34:50: error: expected ':' before ')' token
   34 |        L.push_back(max((!L.empty() ? L.back() ? 0), high[v] + 1));
      |                                                  ^
      |                                                  :
dreaming.cpp:34:50: error: expected primary-expression before ')' token
dreaming.cpp:37:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |    for(int i = 0; i < k.size(); i ++) {
      |                   ~~^~~~~~~~~~
dreaming.cpp:39:8: error: 'R' was not declared in this scope
   39 |        R.push_back(max((!R.empty() ? R.back() ? 0), high[v] + 1));
      |        ^
dreaming.cpp:39:50: error: expected ':' before ')' token
   39 |        R.push_back(max((!R.empty() ? R.back() ? 0), high[v] + 1));
      |                                                  ^
      |                                                  :
dreaming.cpp:39:50: error: expected primary-expression before ')' token
dreaming.cpp:39:50: error: expected ':' before ')' token
   39 |        R.push_back(max((!R.empty() ? R.back() ? 0), high[v] + 1));
      |                                                  ^
      |                                                  :
dreaming.cpp:39:50: error: expected primary-expression before ')' token
dreaming.cpp:42:12: error: 'R' was not declared in this scope
   42 |    reverse(R.begin(), R.end());
      |            ^
dreaming.cpp:44:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |    for(int i = 0; i < k.size(); i ++) {
      |                   ~~^~~~~~~~~~
dreaming.cpp:49:39: error: 'L' was not declared in this scope
   49 |        if(i) _high[v] = max(_high[v], L[i - 1] + 1);
      |                                       ^
dreaming.cpp: In function 'int travelTime(int, int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
dreaming.cpp:58:41: error: no matching function for call to 'std::vector<int>::push_back(<brace-enclosed initializer list>)'
   58 |         adj[A[i]].push_back({B[i], T[i]});
      |                                         ^
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:2:
/usr/include/c++/10/bits/stl_vector.h:1187:7: note: candidate: 'void std::vector<_Tp, _Alloc>::push_back(const value_type&) [with _Tp = int; _Alloc = std::allocator<int>; std::vector<_Tp, _Alloc>::value_type = 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 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 = int; _Alloc = std::allocator<int>; std::vector<_Tp, _Alloc>::value_type = 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<int>::value_type&&' {aka 'int&&'}
 1203 |       push_back(value_type&& __x)
      |                 ~~~~~~~~~~~~~^~~
dreaming.cpp:59:41: error: no matching function for call to 'std::vector<int>::push_back(<brace-enclosed initializer list>)'
   59 |         adj[B[i]].push_back({A[i], T[i]});
      |                                         ^
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:2:
/usr/include/c++/10/bits/stl_vector.h:1187:7: note: candidate: 'void std::vector<_Tp, _Alloc>::push_back(const value_type&) [with _Tp = int; _Alloc = std::allocator<int>; std::vector<_Tp, _Alloc>::value_type = 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 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 = int; _Alloc = std::allocator<int>; std::vector<_Tp, _Alloc>::value_type = 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<int>::value_type&&' {aka 'int&&'}
 1203 |       push_back(value_type&& __x)
      |                 ~~~~~~~~~~~~~^~~