oj.uz

답안 #419605

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
419605 2021-06-07T10:08:47 Z keta_tsimakuridze Zagrade (COI17_zagrade) C++14
100 / 100
 1520 ms 52008 KB 
#include<bits/stdc++.h>
#define f first
#define s second
#define int long long
using namespace std;
const int N=3e5+5,mod=1e9+7;
int t,ans,sz[N],c[N],fix[N],n,centroid,ans_;
vector<int>V[N];
map<int,int> cnt;
void get_szs(int u,int p){
	sz[u] = 1;
	for(int i=0;i<V[u].size();i++){
		if(V[u][i]==p || fix[V[u][i]]) continue;
		get_szs(V[u][i],u);
		sz[u] += sz[V[u][i]];
	}
}
int find_centroid(int u,int p,int Sz){
	for(int i=0;i<V[u].size();i++){
		if(V[u][i]==p || fix[V[u][i]]) continue;
		if(sz[V[u][i]] >Sz/2) return find_centroid(V[u][i],u,Sz);
	}
	return u;
}
void half2(int u,int p,int cur,int mn,int x,int y) {

	cur += c[u];
	x+=(c[u]==1);
	mn = min(mn,cur);
	y+=(c[u]==-1);
	if(y-x >= abs(mn))ans += cnt[y-x];
	if(mn+c[centroid] >= 0 && cur+c[centroid] == 0 )  ans_++;

	for(int i=0;i<V[u].size();i++){
		if(V[u][i] == p || fix[V[u][i]]) continue;
	
		half2(V[u][i],u,cur,mn,x,y);
	}
}
void half1(int u,int p,int cur,int mx,int x,int y) {
	
	cur += c[u];
	x+=(c[u]==1);
	mx = max(mx,cur); 
	y+=(c[u]==-1); 
	if(cur-mx >= 0) cnt[x-y]++;
	if(cur-mx >= 0 && cur==0) ans_++;
	for(int i=0;i<V[u].size();i++) {
		if(V[u][i] == p || fix[V[u][i]]) continue;
		half1(V[u][i],u,cur,mx,x,y);
	}
}
void centroid_decomp(int u){
	get_szs(u,0);
	int C = find_centroid(u,0,sz[u]);
	fix[C] = 1; 
	centroid=C;

	cnt.clear();
	ans_ = 0;
	for(int i=0;i<V[C].size();i++){
		if(fix[V[C][i]]) continue;
		half2(V[C][i],C,0,0,0,0);
		half1(V[C][i],C,c[C],max(0ll,c[C]),c[C] == 1,c[C]==-1);
	}
	reverse(V[C].begin(),V[C].end());
	cnt.clear();
	for(int i=0;i<V[C].size();i++){
		if(fix[V[C][i]]) continue;
		half2(V[C][i],C,0,0,0,0);
		half1(V[C][i],C,c[C],max(0ll,c[C]),c[C] == 1,c[C]==-1);
	} ans += ans_/2;
	for(int i=0;i<V[C].size();i++){
		if(fix[V[C][i]]) continue;
		centroid_decomp(V[C][i]);
	}
}
main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		char ch;
		cin>>ch;
		if(ch=='(') c[i] = 1;
		else c[i] = -1;
	}
	for(int i=2;i<=n;i++){
		int u,v;
		cin>>u>>v;
		V[u].push_back(v);
		V[v].push_back(u);
	}
	centroid_decomp(1);
	cout<<ans;
}

Compilation message

zagrade.cpp: In function 'void get_szs(long long int, long long int)':
zagrade.cpp:12:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |  for(int i=0;i<V[u].size();i++){
      |              ~^~~~~~~~~~~~
zagrade.cpp: In function 'long long int find_centroid(long long int, long long int, long long int)':
zagrade.cpp:19:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |  for(int i=0;i<V[u].size();i++){
      |              ~^~~~~~~~~~~~
zagrade.cpp: In function 'void half2(long long int, long long int, long long int, long long int, long long int, long long int)':
zagrade.cpp:34:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |  for(int i=0;i<V[u].size();i++){
      |              ~^~~~~~~~~~~~
zagrade.cpp: In function 'void half1(long long int, long long int, long long int, long long int, long long int, long long int)':
zagrade.cpp:48:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |  for(int i=0;i<V[u].size();i++) {
      |              ~^~~~~~~~~~~~
zagrade.cpp: In function 'void centroid_decomp(long long int)':
zagrade.cpp:61:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |  for(int i=0;i<V[C].size();i++){
      |              ~^~~~~~~~~~~~
zagrade.cpp:68:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |  for(int i=0;i<V[C].size();i++){
      |              ~^~~~~~~~~~~~
zagrade.cpp:73:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |  for(int i=0;i<V[C].size();i++){
      |              ~^~~~~~~~~~~~
zagrade.cpp: At global scope:
zagrade.cpp:78:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   78 | main(){
      | ^~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 7372 KB Output is correct
2 Correct 5 ms 7372 KB Output is correct
3 Correct 5 ms 7372 KB Output is correct
4 Correct 6 ms 7444 KB Output is correct
5 Correct 5 ms 7448 KB Output is correct
6 Correct 7 ms 7372 KB Output is correct
7 Correct 6 ms 7372 KB Output is correct
8 Correct 5 ms 7372 KB Output is correct
9 Correct 7 ms 7372 KB Output is correct
10 Correct 5 ms 7356 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 640 ms 42552 KB Output is correct
2 Correct 949 ms 46256 KB Output is correct
3 Correct 636 ms 42720 KB Output is correct
4 Correct 840 ms 45296 KB Output is correct
5 Correct 618 ms 42612 KB Output is correct
6 Correct 728 ms 43844 KB Output is correct
7 Correct 603 ms 42692 KB Output is correct
8 Correct 735 ms 43892 KB Output is correct
9 Correct 613 ms 42532 KB Output is correct
10 Correct 1289 ms 51940 KB Output is correct
11 Correct 527 ms 42564 KB Output is correct

Subtask #3
60.0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 7372 KB Output is correct
2 Correct 5 ms 7372 KB Output is correct
3 Correct 5 ms 7372 KB Output is correct
4 Correct 6 ms 7444 KB Output is correct
5 Correct 5 ms 7448 KB Output is correct
6 Correct 7 ms 7372 KB Output is correct
7 Correct 6 ms 7372 KB Output is correct
8 Correct 5 ms 7372 KB Output is correct
9 Correct 7 ms 7372 KB Output is correct
10 Correct 5 ms 7356 KB Output is correct
11 Correct 640 ms 42552 KB Output is correct
12 Correct 949 ms 46256 KB Output is correct
13 Correct 636 ms 42720 KB Output is correct
14 Correct 840 ms 45296 KB Output is correct
15 Correct 618 ms 42612 KB Output is correct
16 Correct 728 ms 43844 KB Output is correct
17 Correct 603 ms 42692 KB Output is correct
18 Correct 735 ms 43892 KB Output is correct
19 Correct 613 ms 42532 KB Output is correct
20 Correct 1289 ms 51940 KB Output is correct
21 Correct 527 ms 42564 KB Output is correct
22 Correct 1458 ms 25580 KB Output is correct
23 Correct 1496 ms 25612 KB Output is correct
24 Correct 1329 ms 25608 KB Output is correct
25 Correct 1520 ms 25608 KB Output is correct
26 Correct 701 ms 31380 KB Output is correct
27 Correct 711 ms 28564 KB Output is correct
28 Correct 734 ms 27420 KB Output is correct
29 Correct 1277 ms 52008 KB Output is correct
30 Correct 1259 ms 51956 KB Output is correct
31 Correct 115 ms 26496 KB Output is correct
32 Correct 523 ms 42472 KB Output is correct