답안 #66346 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
66346	2018-08-10T09:28:04 Z	MrTEK	Zagrade (COI17_zagrade)	C++14	100 / 100	1083 ms	81164 KB

zagrade

#include <bits/stdc++.h>

using namespace std;
#define mp make_pair
#define pb push_back
#define len(a) (int)a.size()
#define fi first
#define sc second
#define d1(w) cerr<<#w<<":"<<w<<endl;
#define d2(w,c) cerr<<#w<<":"<<w<<" "<<#c<<":"<<c<<endl;
#define d3(w,c,z) cerr<<#w<<":"<<w<<" "<<#c<<":"<<c<<" "<<#z<<":"<<z<<endl;
#define left ind+ind
#define right ind+ind+1
#define mid (l+r)/2
#define FAST_IO ios_base::sync_with_stdio(false);
#define endl '\n'

typedef long long int ll;

const int maxn = 620;
const long long LINF = 1e18;
const int LOG = 31;
const int INF = 1e9;
const int N = 3e5 + 5;
const int M = 25;
const int SQ = 350;
const int MOD = 998244353;

typedef pair <int,int> pii;

vector <int> ed[N],vec,vec2,v;

long long int ans = 0;

int n,sub[N],a[N],vis[N],mark[N],mark2[N];

int calc(int cur,int back = -1) {
	sub[cur] = 0;
	for (auto i : ed[cur])
		if (i != back && !vis[i])
			sub[cur] += calc(i,cur);
	return ++sub[cur];
}

int find(int cur,int back,int size) {
	for (auto i : ed[cur])
		if (i != back && !vis[i] && sub[i] > size / 2)
			return find(i,cur,size);
	return cur;
}

void dfs(int cur,int back,int sm,int mx,int sm2,int mx2) {
	sm += a[cur];
	sm2 -= a[cur];
	mx = max(mx,sm);
	mx2 = max(mx2,sm2);
	if (sm == mx && sm >=0 ) vec.pb(sm);
	if (sm2 == mx2 && sm2 >= 0) vec2.pb(sm2);	
	for (auto i : ed[cur]) {
		if (i == back || vis[i] == 1) continue;
		dfs(i,cur,sm,mx,sm2,mx2);
	}
}

void dfs2(int cur,int back,int sm,int mn,int sm2,int mn2) {
	sm += a[cur];
	sm2 -= a[cur];
	mn = min(mn,sm);
	mn2 = min(mn2,sm2);
	if (sm == mn && sm <= 0) ans += mark[-sm];
	if (sm2 == mn2 && sm2 <= 0) ans += mark2[-sm2];
	for (auto i : ed[cur]) {
		if (i == back || vis[i] == 1) continue;
		dfs2(i,cur,sm,mn,sm2,mn2);
	}
}

void solve(int cur = 1) {

	int cen = find(cur,-1,calc(cur));

	vis[cen] = 1;

	for (auto i : ed[cen]) {
		if (vis[i]) continue;
		vec.clear();
		vec2.clear();
		dfs2(i,-1,0,INF,0,INF);
		dfs(i,-1,0,-INF,0,-INF);
		// if (cen == 2) d1(i);
		// if (cen == 2) for (auto j : vec) d1(j);
		for (auto j : vec) if (j + a[cen] >= 0) {mark[j + a[cen]]++; if (j + a[cen] == 0) ans++; v.pb(j + a[cen]);} 
		for (auto j : vec2) if (j - a[cen] >= 0) { mark2[j - a[cen]]++; if (j - a[cen] == 0) ans++; v.pb(j - a[cen]);}
	}
	
	// d2(cen,ans);

	for (auto i : v) mark[i] = mark2[i] = 0;

	v.clear();

	for (auto i : ed[cen])
		if (!vis[i])
			solve(i);
}

int main() {

	scanf("%d",&n);

	for (int i = 1 ; i <= n; i++) {
		char c;
		scanf(" %c",&c);
		if (c == '(') a[i] = 1;
		else a[i] = -1;
	}

	for (int i = 1 ; i < n ; i++) {
		int u,v;
		scanf("%d %d",&u,&v);
		ed[u].pb(v);
		ed[v].pb(u);
	}

	solve();

	printf("%lld\n",ans);

	return 0 ;
}

Compilation message

zagrade.cpp: In function 'int main()':
zagrade.cpp:109:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
zagrade.cpp:113:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c",&c);
   ~~~~~^~~~~~~~~~
zagrade.cpp:120:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&u,&v);
   ~~~~~^~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	10 ms	7416 KB	Output is correct
2	Correct	11 ms	7528 KB	Output is correct
3	Correct	9 ms	7776 KB	Output is correct
4	Correct	9 ms	7776 KB	Output is correct
5	Correct	11 ms	7776 KB	Output is correct
6	Correct	11 ms	7776 KB	Output is correct
7	Correct	10 ms	7864 KB	Output is correct
8	Correct	10 ms	7924 KB	Output is correct
9	Correct	11 ms	7924 KB	Output is correct
10	Correct	9 ms	7988 KB	Output is correct

Subtask #2
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	407 ms	34972 KB	Output is correct
2	Correct	481 ms	36644 KB	Output is correct
3	Correct	433 ms	36644 KB	Output is correct
4	Correct	454 ms	36644 KB	Output is correct
5	Correct	465 ms	36644 KB	Output is correct
6	Correct	477 ms	36644 KB	Output is correct
7	Correct	463 ms	36644 KB	Output is correct
8	Correct	458 ms	36644 KB	Output is correct
9	Correct	409 ms	36644 KB	Output is correct
10	Correct	425 ms	38592 KB	Output is correct
11	Correct	443 ms	38592 KB	Output is correct

Subtask #3
60.0 / 60.0

#	결과	실행 시간	메모리	Grader output
1	Correct	10 ms	7416 KB	Output is correct
2	Correct	11 ms	7528 KB	Output is correct
3	Correct	9 ms	7776 KB	Output is correct
4	Correct	9 ms	7776 KB	Output is correct
5	Correct	11 ms	7776 KB	Output is correct
6	Correct	11 ms	7776 KB	Output is correct
7	Correct	10 ms	7864 KB	Output is correct
8	Correct	10 ms	7924 KB	Output is correct
9	Correct	11 ms	7924 KB	Output is correct
10	Correct	9 ms	7988 KB	Output is correct
11	Correct	407 ms	34972 KB	Output is correct
12	Correct	481 ms	36644 KB	Output is correct
13	Correct	433 ms	36644 KB	Output is correct
14	Correct	454 ms	36644 KB	Output is correct
15	Correct	465 ms	36644 KB	Output is correct
16	Correct	477 ms	36644 KB	Output is correct
17	Correct	463 ms	36644 KB	Output is correct
18	Correct	458 ms	36644 KB	Output is correct
19	Correct	409 ms	36644 KB	Output is correct
20	Correct	425 ms	38592 KB	Output is correct
21	Correct	443 ms	38592 KB	Output is correct
22	Correct	1083 ms	38592 KB	Output is correct
23	Correct	957 ms	38592 KB	Output is correct
24	Correct	1065 ms	38592 KB	Output is correct
25	Correct	1027 ms	38592 KB	Output is correct
26	Correct	560 ms	46196 KB	Output is correct
27	Correct	500 ms	48468 KB	Output is correct
28	Correct	591 ms	51896 KB	Output is correct
29	Correct	477 ms	71556 KB	Output is correct
30	Correct	448 ms	75772 KB	Output is correct
31	Correct	146 ms	75772 KB	Output is correct
32	Correct	437 ms	81164 KB	Output is correct

답안 #66346

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