답안 #66391 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
66391	2018-08-10T11:13:24 Z	hamzqq9	Zagrade (COI17_zagrade)	C++14	100 / 100	1817 ms	39152 KB

zagrade

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

답안 #66391

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 30.0 / 30.0

Subtask #3 60.0 / 60.0

Subtask #1
10.0 / 10.0

Subtask #2
30.0 / 30.0

Subtask #3
60.0 / 60.0