oj.uz

Submission #245710

# Submission time Handle Problem Language Result Execution time Memory
245710 2020-07-07T08:44:19 Z vanic Zagrade (COI17_zagrade) C++14
100 / 100
 1280 ms 57348 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7424 KB Output is correct
2 Correct 9 ms 7424 KB Output is correct
3 Correct 11 ms 7424 KB Output is correct
4 Correct 10 ms 7424 KB Output is correct
5 Correct 11 ms 7424 KB Output is correct
6 Correct 9 ms 7424 KB Output is correct
7 Correct 10 ms 7424 KB Output is correct
8 Correct 10 ms 7424 KB Output is correct
9 Correct 10 ms 7424 KB Output is correct
10 Correct 10 ms 7424 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 440 ms 42504 KB Output is correct
2 Correct 774 ms 48548 KB Output is correct
3 Correct 475 ms 42608 KB Output is correct
4 Correct 723 ms 47116 KB Output is correct
5 Correct 469 ms 42764 KB Output is correct
6 Correct 545 ms 44600 KB Output is correct
7 Correct 452 ms 42508 KB Output is correct
8 Correct 566 ms 44620 KB Output is correct
9 Correct 447 ms 42508 KB Output is correct
10 Correct 1153 ms 57220 KB Output is correct
11 Correct 377 ms 43676 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7424 KB Output is correct
2 Correct 9 ms 7424 KB Output is correct
3 Correct 11 ms 7424 KB Output is correct
4 Correct 10 ms 7424 KB Output is correct
5 Correct 11 ms 7424 KB Output is correct
6 Correct 9 ms 7424 KB Output is correct
7 Correct 10 ms 7424 KB Output is correct
8 Correct 10 ms 7424 KB Output is correct
9 Correct 10 ms 7424 KB Output is correct
10 Correct 10 ms 7424 KB Output is correct
11 Correct 440 ms 42504 KB Output is correct
12 Correct 774 ms 48548 KB Output is correct
13 Correct 475 ms 42608 KB Output is correct
14 Correct 723 ms 47116 KB Output is correct
15 Correct 469 ms 42764 KB Output is correct
16 Correct 545 ms 44600 KB Output is correct
17 Correct 452 ms 42508 KB Output is correct
18 Correct 566 ms 44620 KB Output is correct
19 Correct 447 ms 42508 KB Output is correct
20 Correct 1153 ms 57220 KB Output is correct
21 Correct 377 ms 43676 KB Output is correct
22 Correct 779 ms 24704 KB Output is correct
23 Correct 792 ms 24484 KB Output is correct
24 Correct 840 ms 24440 KB Output is correct
25 Correct 810 ms 24416 KB Output is correct
26 Correct 478 ms 30096 KB Output is correct
27 Correct 501 ms 27468 KB Output is correct
28 Correct 475 ms 26124 KB Output is correct
29 Correct 1280 ms 57304 KB Output is correct
30 Correct 1267 ms 57348 KB Output is correct
31 Correct 129 ms 24960 KB Output is correct
32 Correct 372 ms 43656 KB Output is correct