Submission #743748

#	Time	Username	Problem	Language	Result	Execution time	Memory
743748		nvujica	Zagrade (COI17_zagrade)	C++14	100 / 100	277 ms	75120 KiB

zagrade

#include <bits/stdc++.h>

#define ll long long
#define fi first
#define se second

using namespace std;

const int maxn = 3e5 + 10;

int n;
ll sol;
int a[maxn];
set <pair<int, int> > s[maxn];
vector <int> v[maxn];
int d[maxn];

void spoji(int x, int y){
//	cout << x << ' ' << y << endl;
	
	auto it = s[y].lower_bound({-d[y] - a[x], 0});
	if(it != s[y].end() && (*it).fi == -d[y] - a[x]) s[y].erase(it);
	
	//cout << "jos sam tu" << endl;
	
	int y2 = y;
	
	if(s[x].size() < s[y].size()){
		swap(s[x], s[y]);
		swap(d[x], d[y]);
		y2 = x;
	}
	
	vector <pair<int, int> > t;
	
	while(!s[y].empty()){
		//cout << "tu sam" << endl;
		
		int br = s[y].begin() -> fi;
		int cnt = s[y].begin() -> se;
		s[y].erase(s[y].begin());
		t.push_back({br, cnt});
		
		auto it = s[x].lower_bound({-(br + d[y]) - d[x], 0});
		if(it != s[x].end() && (*it).fi == -(br + d[y]) - d[x]){
			sol += cnt * (*it).se;
			
//			cout << x << ' ' << y << ' ' << cnt << ' ' << (*it).se << endl;
		}
	}
	
	d[y2] += a[x];
	
	for(int i = 0; i < t.size(); i++){
		int br = t[i].fi;
		int cnt = t[i].se;
		
		//cout << br << ' ' << cnt;
		
		auto it = s[x].lower_bound({br + d[y] - d[x], 0});
		if(it != s[x].end() && (*it).fi == br + d[y] - d[x]){
			cnt += (*it).se;
			s[x].erase(it);
		}
		
		s[x].insert({br + d[y] - d[x], cnt});
	}
}

void rek(int x, int p){
	s[x].insert({2 * a[x], 1});
	
	for(int i = 0; i < v[x].size(); i++){
		int x2 = v[x][i];
		
		if(x2 == p) continue;
		
		rek(x2, x);
		
		spoji(x, x2);
	}
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;
	
	for(int i = 1; i <= n; i++){
		char c;
		cin >> c;
		
		if(c == '(') a[i] = 1; 
		else a[i] = -1; 
	}
	
	for(int i = 0; i < n - 1; i++){
		int x, y;
		cin >> x >> y;
		
		v[x].push_back(y);
		v[y].push_back(x);
	}
	
	rek(1, 0);
	
	cout << sol;

	return 0;
}

Compilation message (stderr)

zagrade.cpp: In function 'void spoji(int, int)':
zagrade.cpp:54:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |  for(int i = 0; i < t.size(); i++){
      |                 ~~^~~~~~~~~~
zagrade.cpp: In function 'void rek(int, int)':
zagrade.cpp:73:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |  for(int i = 0; i < v[x].size(); i++){
      |                 ~~^~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 30 / 30
• Subtask 3: 60 / 60