Submission #1181292

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181292		KK_1729	Meetings 2 (JOI21_meetings2)	C++20	Compilation error	0 ms	0 KiB

meetings2

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

// #define int long long
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define pb push_back
#define all(a) a.begin(), a.end()
#define endl "\n"

void printVector(vector<int> a){
	for (auto x: a) cout << x << " ";
	cout << endl;
}
vector<vector<int>> graph;
vector<int> subtree, subtree1;
vector<int> vis;
int dp(int x, int p = -1){
    if (vis[x]) return 0;
    subtree[x] = 1;
    for (auto node: graph[x]){
        if (node == p) continue;
        subtree[x] += dp(node, x);
    }
    return subtree[x];
}
int find_centroid(int x, int p, int n){
    for (auto node: graph[x]){
        if (node == p) continue;
        if (!vis[node] && subtree[node]*2 > n) return find_centroid(node, x, n);
    }
    return x;
}
vector<int> curr;
vector<int> o;
vector<int> depth;
int dp1(int x, int p = -1, int e = 0){
	if (vis[x]) return 0;
	o[x] = e;
	curr.pb(x);
	subtree1[x] = 1;
	for (auto node: graph[x]){
		if (node == p) continue;
		depth[node] = depth[x]+1;
		subtree1[x] += dp1(node, x, e);
	}
	return subtree1[x];
}
vector<int> answer;
void init_centroid(int x = 1, int p = -1){
    dp(x);
    int c = find_centroid(x, -1, subtree[x]);
    // cout << c << endl;
    vector<int> candidates;
    for (auto item: graph[c]){
    	if (!vis[item]) candidates.pb(item);
    }
    for (auto d: candidates){
        depth[d] = 1;
    	dp1(d, c, d);
    }
    vector<vector<int>> opt;
    for (auto item: curr){
    	opt.pb({subtree1[item], depth[item], o[item]});
    }
    sort(all(opt));
    reverse(all(opt));
    map<int, int> e;
   	multiset<int, greater<int>> k;
   	for (auto item: candidates){
   		e[item] = 0;
   		k.insert(0);
   	}
   	k.insert(0);
   	k.insert(0);
   	int ind = 0;
   	int at = curr.size()+1;
   	if (at%2 == 1) at--;
   	while (at > 0){
   	    while (ind < opt.size() && opt[ind][0] >= at/2){
   	        vector<int> op = opt[ind];
       		k.erase(k.find(e[op[2]]));
       		e[op[2]] = max(e[op[2]], op[1]);
       		k.insert(e[op[2]]);
       		ind++;
   	    }
   		auto t = k.begin();
   		int s = *t;
   		t++;
   		s += *t;
   		answer[at] = max(answer[at], s+1ll);
   		at -= 2;
   	}

    for (auto x: curr){
    	subtree[x] = 0;
    	o[x] = 0;
    	depth[x] = 0;
    }
    e.clear();
    k.clear();

    vis[c] = 1;
    // ctree[c] = p;
 	curr.clear();
    for (int node: graph[c]){
        if (!vis[node]){
            init_centroid(node, c);
        }
    }
}
void solve(){
	int n; cin >> n;
	graph.resize(n+1);
	subtree.resize(n+1);
	subtree1.resize(n+1);
	o.resize(n+1);
	vis.resize(n+1);
	answer.resize(n+5);
	depth.resize(n+1);

	FOR(i,0,n-1){
		int u, v; cin >> u >> v;

		graph[u].pb(v);
		graph[v].pb(u);
	}
	init_centroid(1);
	for (int i = 1; i <= n; ++i){
	    if (i%2 == 1) cout << 1 << endl;
	    else{
	        cout << answer[i] << endl;
	    }
	}
}


int32_t main(){
	ios::sync_with_stdio(false);cin.tie(nullptr);
	int t = 1; // cin >> t;
	while (t--) solve();
}

Compilation message (stderr)

meetings2.cpp: In function 'void init_centroid(int, int)':
meetings2.cpp:90:33: error: no matching function for call to 'max(__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type&, long long int)'
   90 |                 answer[at] = max(answer[at], s+1ll);
      |                              ~~~^~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/bits/specfun.h:45,
                 from /usr/include/c++/11/cmath:1935,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from meetings2.cpp:1:
/usr/include/c++/11/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  254 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/11/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
meetings2.cpp:90:33: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
   90 |                 answer[at] = max(answer[at], s+1ll);
      |                              ~~~^~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/bits/specfun.h:45,
                 from /usr/include/c++/11/cmath:1935,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from meetings2.cpp:1:
/usr/include/c++/11/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  300 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/11/bits/stl_algobase.h:300:5: note:   template argument deduction/substitution failed:
meetings2.cpp:90:33: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
   90 |                 answer[at] = max(answer[at], s+1ll);
      |                              ~~~^~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/string:52,
                 from /usr/include/c++/11/bits/locale_classes.h:40,
                 from /usr/include/c++/11/bits/ios_base.h:41,
                 from /usr/include/c++/11/ios:42,
                 from /usr/include/c++/11/istream:38,
                 from /usr/include/c++/11/sstream:38,
                 from /usr/include/c++/11/complex:45,
                 from /usr/include/c++/11/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
                 from meetings2.cpp:1:
/usr/include/c++/11/bits/stl_algo.h:3461:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
 3461 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/11/bits/stl_algo.h:3461:5: note:   template argument deduction/substitution failed:
meetings2.cpp:90:33: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   90 |                 answer[at] = max(answer[at], s+1ll);
      |                              ~~~^~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/string:52,
                 from /usr/include/c++/11/bits/locale_classes.h:40,
                 from /usr/include/c++/11/bits/ios_base.h:41,
                 from /usr/include/c++/11/ios:42,
                 from /usr/include/c++/11/istream:38,
                 from /usr/include/c++/11/sstream:38,
                 from /usr/include/c++/11/complex:45,
                 from /usr/include/c++/11/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
                 from meetings2.cpp:1:
/usr/include/c++/11/bits/stl_algo.h:3467:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
 3467 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/11/bits/stl_algo.h:3467:5: note:   template argument deduction/substitution failed:
meetings2.cpp:90:33: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   90 |                 answer[at] = max(answer[at], s+1ll);
      |                              ~~~^~~~~~~~~~~~~~~~~~~