Submission #245710

#	Time	Username	Problem	Language	Result	Execution time	Memory
245710		vanic	Zagrade (COI17_zagrade)	C++14	100 / 100	1280 ms	57348 KiB

zagrade

#include <iostream>
#include <cstdio>
#include <math.h>
#include <set>
#include <algorithm>
#include <stack>
#include <vector>
#include <map>
#include <string.h>
#include <queue>
#include <array>
#include <bitset>

using namespace std;

const int maxn=3e5+5;
typedef long long ll;

map < int, int > m;
vector < int > upd;
vector < int > ms[maxn];
int val[maxn];
bitset < maxn > bio;
int vel[maxn];
ll sol;

int dfs(int x, int prosl){
	vel[x]=1;
	for(int i=0; i<ms[x].size(); i++){
		if(ms[x][i]!=prosl && !bio[ms[x][i]]){
			vel[x]+=dfs(ms[x][i], x);
		}
	}
	return vel[x];
}

int centroid(int x, int val){
	for(int i=0; i<ms[x].size(); i++){
		if(!bio[ms[x][i]] && vel[ms[x][i]]>val/2 && vel[ms[x][i]]<vel[x]){
			return centroid(ms[x][i], val);
		}
	}
	return x;
}

int poc;

void siri(int x, int prosl, int br, int mini, int maksi){
	br+=val[x];
	mini=min(mini, br);
	maksi=max(maksi, br);
	if(val[x]==-1){
		if(br-mini<=0 && br+poc<=0){
			sol+=m[-(br+poc)];
			upd.push_back(br);
		}
	}
	else{
		if(br-maksi>=0 && br+poc>=0){
			sol+=m[-(br+poc)];
			upd.push_back(br);
		}
	}
	for(int i=0; i<ms[x].size(); i++){
		if(ms[x][i]!=prosl && !bio[ms[x][i]]){
			siri(ms[x][i], x, br, mini, maksi);
		}
	}
}

void solve(int x){
	m[0]=1;
	poc=val[x];
	int prosl=sol;
	for(int i=0; i<ms[x].size(); i++){
		if(!bio[ms[x][i]]){
			siri(ms[x][i], x, 0, 0, 0);
			while(!upd.empty()){
				m[upd.back()]++;
				upd.pop_back();
			}
		}
	}
	m.clear();
}

void rijesi(int x, int val){
	dfs(x, -1);
	x=centroid(x, val);
//	cout << x << endl;
	solve(x);
	bio[x]=1;
	int y;
	for(int i=0; i<ms[x].size(); i++){
		if(!bio[ms[x][i]]){
			if(vel[ms[x][i]]>vel[x]){
				y=val-vel[x];
			}
			else{
				y=vel[ms[x][i]];
			}
			rijesi(ms[x][i], y);
		}
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin >> n;
	string s;
	cin >> s;
	int a, b;
	for(int i=0; i<n-1; i++){
		cin >> a >> b;
		a--;
		b--;
		ms[a].push_back(b);
		ms[b].push_back(a);
	}
	for(int i=0; i<n; i++){
		if(s[i]=='('){
			val[i]=1;
		}
		else{
			val[i]=-1;
		}
	}
	rijesi(0, n);
	cout << sol << '\n';
	return 0;
}

Compilation message (stderr)

zagrade.cpp: In function 'int dfs(int, int)':
zagrade.cpp:29:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<ms[x].size(); i++){
               ~^~~~~~~~~~~~~
zagrade.cpp: In function 'int centroid(int, int)':
zagrade.cpp:38:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<ms[x].size(); i++){
               ~^~~~~~~~~~~~~
zagrade.cpp: In function 'void siri(int, int, int, int, int)':
zagrade.cpp:64:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<ms[x].size(); i++){
               ~^~~~~~~~~~~~~
zagrade.cpp: In function 'void solve(int)':
zagrade.cpp:75:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<ms[x].size(); i++){
               ~^~~~~~~~~~~~~
zagrade.cpp:74:6: warning: unused variable 'prosl' [-Wunused-variable]
  int prosl=sol;
      ^~~~~
zagrade.cpp: In function 'void rijesi(int, int)':
zagrade.cpp:94:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<ms[x].size(); i++){
               ~^~~~~~~~~~~~~

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