oj.uz

Submission #66391

# Submission time Handle Problem Language Result Execution time Memory
66391 2018-08-10T11:13:24 Z hamzqq9 Zagrade (COI17_zagrade) C++14
100 / 100
 1817 ms 39152 KB 
#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define ppb pop_back
#define umax(x,y) x=max(x,y)
#define umin(x,y) x=min(x,y)
#define ll long long
#define ii pair<int,int>
#define iii pair<ii,int>
#define sz(x) (x.size())
#define orta ((bas+son)>>1)
#define all(x) x.begin(),x.end()
#define dbgs(x) cerr<<(#x)<<" --> "<<(x)<<" "
#define dbg(x) cerr<<(#x)<<" --> "<<(x)<<endl;getchar()
#define pw(x) (1<<(x))
#define inf 1000000000
#define MOD 1000000007
#define N 300005
#define MAX 10000006
#define LOG 20
#define count anan
using namespace std;

int sub[N],F[N],count[N];
int n,x,y,Gsub;
ll ans;
vector<int> v[N];
char s[N];

void dfs_to(int node,int ata,int bal,int prob,int add) {

	if(bal==0 && s[node]=='(') prob++;

	bal=min(0,bal+(s[node]=='('?1:-1));

	if(bal==0) count[prob]+=add;

	for(int i:v[node]) {

		if(i==ata || F[i]) continue ;

		dfs_to(i,node,bal,prob,add); 

	}

}

void dfs_from(int node,int ata,int bal,int prob) {

	if(bal==0 && s[node]==')') prob++;

	bal=max(0,bal+(s[node]=='('?1:-1));

	if(bal==0) ans+=count[prob];

	for(int i:v[node]) {

		if(i==ata || F[i]) continue ;

		dfs_from(i,node,bal,prob);

	}

}

void fsubs(int node,int ata) {

	sub[node]=1;

	for(int i:v[node]) {
		
		if(i==ata || F[i]) continue ;

		fsubs(i,node);

		sub[node]+=sub[i];

	}

}

int fcnt(int node,int ata) {

	for(int i:v[node]) {

		if(i==ata || F[i]) continue ;

		if(sub[i]>Gsub/2) return fcnt(i,node);

	}

	return node;

}

void solve(int node) {

	fsubs(node,0);

	Gsub=sub[node];

	int cnt=fcnt(node,0);

	F[cnt]=1;

	count[0]++;

	for(int i:v[cnt]) {

		if(F[i]) continue ;

		dfs_from(i,cnt,s[cnt]=='(',s[cnt]==')');

		dfs_to(i,cnt,0,0,1);

	}

	if(s[cnt]==')') ans+=count[1];

	for(int i:v[cnt]) {

		if(F[i]) continue ;

		dfs_to(i,cnt,0,0,-1);

	}

//	printf("PHCNT %d A %d\n",cnt,ans);

	reverse(all(v[cnt]));

	count[0]--;

	for(int i:v[cnt]) {

		if(F[i]) continue ;

		dfs_from(i,cnt,s[cnt]=='(',s[cnt]==')');

		dfs_to(i,cnt,0,0,1);

	}

	for(int i:v[cnt]) {

		if(F[i]) continue ;

		dfs_to(i,cnt,0,0,-1);

	}	

//	printf("C%d A%d\n",cnt,ans);

	for(int i:v[cnt]) {

		if(F[i]) continue ;

		solve(i);

	}

}

int main() {

//	freopen("input.txt","r",stdin);

	scanf("%d",&n);

	scanf("%s",s+1);

	for(int i=1;i<n;i++) {

		scanf("%d %d",&x,&y);

		v[x].pb(y);
		v[y].pb(x);

	}

	solve(1);

	printf("%lld",ans);

}

Compilation message

zagrade.cpp: In function 'int main()':
zagrade.cpp:169:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
zagrade.cpp:171:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s",s+1);
  ~~~~~^~~~~~~~~~
zagrade.cpp:175:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&x,&y);
   ~~~~~^~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 707 ms 38640 KB Output is correct
2 Correct 636 ms 38640 KB Output is correct
3 Correct 632 ms 38640 KB Output is correct
4 Correct 693 ms 38640 KB Output is correct
5 Correct 696 ms 38640 KB Output is correct
6 Correct 678 ms 38692 KB Output is correct
7 Correct 679 ms 38692 KB Output is correct
8 Correct 713 ms 38692 KB Output is correct
9 Correct 697 ms 38692 KB Output is correct
10 Correct 666 ms 39056 KB Output is correct
11 Correct 636 ms 39056 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 7416 KB Output is correct
2 Correct 11 ms 7528 KB Output is correct
3 Correct 11 ms 7528 KB Output is correct
4 Correct 9 ms 7536 KB Output is correct
5 Correct 9 ms 7536 KB Output is correct
6 Correct 10 ms 7548 KB Output is correct
7 Correct 11 ms 7548 KB Output is correct
8 Correct 10 ms 7560 KB Output is correct
9 Correct 9 ms 7560 KB Output is correct
10 Correct 10 ms 7560 KB Output is correct
11 Correct 707 ms 38640 KB Output is correct
12 Correct 636 ms 38640 KB Output is correct
13 Correct 632 ms 38640 KB Output is correct
14 Correct 693 ms 38640 KB Output is correct
15 Correct 696 ms 38640 KB Output is correct
16 Correct 678 ms 38692 KB Output is correct
17 Correct 679 ms 38692 KB Output is correct
18 Correct 713 ms 38692 KB Output is correct
19 Correct 697 ms 38692 KB Output is correct
20 Correct 666 ms 39056 KB Output is correct
21 Correct 636 ms 39056 KB Output is correct
22 Correct 1479 ms 39056 KB Output is correct
23 Correct 1817 ms 39056 KB Output is correct
24 Correct 1397 ms 39056 KB Output is correct
25 Correct 1469 ms 39056 KB Output is correct
26 Correct 808 ms 39056 KB Output is correct
27 Correct 919 ms 39056 KB Output is correct
28 Correct 899 ms 39056 KB Output is correct
29 Correct 613 ms 39152 KB Output is correct
30 Correct 642 ms 39152 KB Output is correct
31 Correct 131 ms 39152 KB Output is correct
32 Correct 625 ms 39152 KB Output is correct