Submission #474670

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
474670	2021-09-19T10:07:49 Z	mychecksedad	Janjetina (COCI21_janjetina)	C++17	Compilation error	0 ms	0 KB

Main

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define pb push_back
#define all(x) x.begin(), x.end()
const int N = 1e5+10;



int n, k, size[N], parent[N], rmq[N][22], r[N];
pair<int, int> arr[N];
ll ans = 0;
vector<pair<int, int>> g[N];
void dfs(int v, int p, int mx, int d){
    for(auto u: g[v]){
        if(u.first != p){
            if(max(mx, u.second) - d - 1 >= k) ++ans;
            dfs(u.first, v, max(mx, u.second), d+1);
        }
    }
}
int find_set(int v){
    if(parent[v] == v) return v;
    return parent[v] = find_set(parent[v]);
}
void union_set(int a, int b){
    a = find_set(a);
    b = find_set(b);
    if(a != b){
        if(size[a] < size[b]) swap(a, b);
        parent[b] = a;
        size[a] += size[b]; 
    }
}
void precalc(){
    for(int i = 1; i < n; i++) rmq[i][0] = r[i];
    for(int j = 1; j < 22; j++){
        for(int i = 1; i <= n; i++){
            rmq[i][j] = max(rmq[i][j - 1], rmq[i + (1<<j)][j - 1]);
        }
    }
}
int mx(int x, int y){
    int k = __lg(y - x + 1);
    return max(rmq[x][k], rmq[y - (1<<k) + 1][k]);
}
int main(){
    cin.tie(0); ios::sync_with_stdio(0);
    cin >> n >> k;
    for(int i = 0; i < n-1; i++){
        int a, b, w;
        cin >> a >> b >> w;
        arr[i + 1] = {w, i};
        r[i + 1] = w; 
        g[a].pb({b, w});
        g[b].pb({a, w});
    }
    precalc();
    if(n <= 1000){
        for(int i = 1; i <= n; i++) dfs(i, 0, 0, 0);
    }else{
        sort(arr + 1, arr + n);
        for(int i = 1; i <= n; i++){
            size[i] = 1;
            parent[i] = i;
        }
        for(int i = 1; i < n; i++){
            int pos = arr[i].second;
            int x = size[find_set(pos)];
            int y = size[find_set(pos+1)];
            int t = mx(pos - x + 1, pos + 1 + y - 2) - k;
            if(x <= t){
                ans += ll(x) * ll(t - x + 1);
                // ans += 
            }
            else{
                ans += ll(min(t, y)) * ll((min(t, y) + 1) / 2);
            }
            union_set(i, i+1);
        }
    }
    cout << ans;

    return 0;
}

Compilation message

Main.cpp: In function 'void union_set(int, int)':
Main.cpp:30:12: error: reference to 'size' is ambiguous
   30 |         if(size[a] < size[b]) swap(a, b);
      |            ^~~~
In file included from /usr/include/c++/10/string:54,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from Main.cpp:1:
/usr/include/c++/10/bits/range_access.h:254:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  254 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/10/bits/range_access.h:245:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  245 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
Main.cpp:10:11: note:                 'int size [100010]'
   10 | int n, k, size[N], parent[N], rmq[N][22], r[N];
      |           ^~~~
Main.cpp:30:22: error: reference to 'size' is ambiguous
   30 |         if(size[a] < size[b]) swap(a, b);
      |                      ^~~~
In file included from /usr/include/c++/10/string:54,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from Main.cpp:1:
/usr/include/c++/10/bits/range_access.h:254:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  254 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/10/bits/range_access.h:245:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  245 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
Main.cpp:10:11: note:                 'int size [100010]'
   10 | int n, k, size[N], parent[N], rmq[N][22], r[N];
      |           ^~~~
Main.cpp:32:9: error: reference to 'size' is ambiguous
   32 |         size[a] += size[b];
      |         ^~~~
In file included from /usr/include/c++/10/string:54,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from Main.cpp:1:
/usr/include/c++/10/bits/range_access.h:254:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  254 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/10/bits/range_access.h:245:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  245 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
Main.cpp:10:11: note:                 'int size [100010]'
   10 | int n, k, size[N], parent[N], rmq[N][22], r[N];
      |           ^~~~
Main.cpp:32:20: error: reference to 'size' is ambiguous
   32 |         size[a] += size[b];
      |                    ^~~~
In file included from /usr/include/c++/10/string:54,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from Main.cpp:1:
/usr/include/c++/10/bits/range_access.h:254:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  254 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/10/bits/range_access.h:245:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  245 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
Main.cpp:10:11: note:                 'int size [100010]'
   10 | int n, k, size[N], parent[N], rmq[N][22], r[N];
      |           ^~~~
Main.cpp: In function 'int main()':
Main.cpp:64:13: error: reference to 'size' is ambiguous
   64 |             size[i] = 1;
      |             ^~~~
In file included from /usr/include/c++/10/string:54,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from Main.cpp:1:
/usr/include/c++/10/bits/range_access.h:254:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  254 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/10/bits/range_access.h:245:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  245 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
Main.cpp:10:11: note:                 'int size [100010]'
   10 | int n, k, size[N], parent[N], rmq[N][22], r[N];
      |           ^~~~
Main.cpp:69:21: error: reference to 'size' is ambiguous
   69 |             int x = size[find_set(pos)];
      |                     ^~~~
In file included from /usr/include/c++/10/string:54,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from Main.cpp:1:
/usr/include/c++/10/bits/range_access.h:254:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  254 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/10/bits/range_access.h:245:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  245 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
Main.cpp:10:11: note:                 'int size [100010]'
   10 | int n, k, size[N], parent[N], rmq[N][22], r[N];
      |           ^~~~
Main.cpp:70:21: error: reference to 'size' is ambiguous
   70 |             int y = size[find_set(pos+1)];
      |                     ^~~~
In file included from /usr/include/c++/10/string:54,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from Main.cpp:1:
/usr/include/c++/10/bits/range_access.h:254:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  254 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/10/bits/range_access.h:245:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  245 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
Main.cpp:10:11: note:                 'int size [100010]'
   10 | int n, k, size[N], parent[N], rmq[N][22], r[N];
      |           ^~~~