| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 144938 |
2019-08-18T07:58:54 Z |
Abelyan |
Zagrade (COI17_zagrade) |
C++17 |
|
1480 ms |
47628 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define FOR(i,a) for (int i=0;i<(a);++i)
#define FORD(i,a) for (int i=(a)-1;i>=0;i--)
#define FORT(i,a,b) for (int i=(a);i<=(b);++i)
#define FORTD(i,b,a) for (int i=(b);i>=(a);--i)
#define trav(i,v) for (auto i : v)
#define all(v) v.begin(),v.end()
#define ad push_back
#define fr first
#define sc second
#define mpr(a,b) make_pair(a,b)
#define pir pair<int,int>
#define all(v) v.begin(),v.end()
#define make_unique(v) v.erase(unique(all(v)),v.end())
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define srng mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define y1 EsiHancagorcRepa
const int N=4e5+10;
const ll MOD2=998244353;
const ll MOD=1e9+7;
char c[N];
int qan=0;
vector<int> g[N],vc;
int sz[N],ans;
bool col[N];
void dfssz(int v,int par=-1){
sz[v]=1;
qan++;
trav(to,g[v]){
if (col[to] || to==par) continue;
dfssz(to,v);
sz[v]+=sz[to];
}
}
int get(int v,int par=-1){
trav(to,g[v]){
if (col[to] || to==par) continue;
if (sz[to]>qan/2) return get(to,v);
}
return v;
}
set<pir> s;
set<pir>::iterator it;
void dfs1(int v,int pr,int mn,int par=-1){
//if (v==3)cout<<v<<" "<<pr<<" "<<mn<<endl;
if (c[v]=='('){
pr++;
mn++;
mn=min(mn,1);
}
else{
pr--;
mn--;
mn=min(mn,-1);
}
//if (v==3)cout<<v<<" "<<pr<<" "<<mn<<endl;
if (mn>=0){
it=s.lower_bound({pr,INT_MIN});
if (it==s.end() || it->fr!=pr){
s.insert({pr,1});
//cout<<v<<" "<<pr<<endl;
}
else{
pir tv=*it;
tv.sc++;
s.erase(it);
s.insert(tv);
//cout<<pr<<endl;
}
}
trav(to,g[v])if (!col[to] && par!=to)dfs1(to,pr,mn,v);
}
void dfs2(int v,int pr,int mn,int par=-1){
if (c[v]=='('){
pr++;
}
else{
pr--;
}
mn=min(mn,pr);
if (mn==pr){
vc.ad(pr);
//cout<<"hey "<<pr<<endl;
}
trav(to,g[v])if (!col[to] && par!=to)dfs2(to,pr,mn,v);
}
void decomp(int v){
qan=0;
dfssz(v);
int cent=get(v);
//cout<<cent<<endl;
FOR(i,g[cent].size()){
int to=g[cent][i];
if (col[to])continue;
dfs2(to,0,0,cent);
trav(tv,vc){
it=s.lower_bound({-tv,INT_MIN});
if (it->fr==-tv){
ans+=it->sc;
}
}
vc.clear();
if (c[cent]=='(')
dfs1(to,1,1,cent);
else dfs1(to,-1,-1,cent);
}
while(!s.empty())s.erase(s.begin());
if (c[cent]=='(')s.insert({1,1});
FORD(i,g[cent].size()){
int to=g[cent][i];
if (col[to])continue;
dfs2(to,0,0,cent);
trav(tv,vc){
//if (c[cent]=='C' && tv==-1)ans++;
it=s.lower_bound({-tv,INT_MIN});
if (it->fr==-tv){
ans+=it->sc;
}
}
vc.clear();
if (c[cent]=='(')
dfs1(to,1,1,cent);
else dfs1(to,-1,-1,cent);
}
it=s.lower_bound({0,INT_MIN});
//cout<<cent<<" "<<ans<<endl;
if (it->fr==0){
ans+=it->sc;
}
while(!s.empty())s.erase(s.begin());
col[cent]=true;
trav(to,g[cent]){
if (!col[to])decomp(to);
}
}
int main(){
fastio;
srng;
#ifdef ALEXPC
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
int n;
cin>>n;
assert(n>=10);
FORT(i,1,n){
cin>>c[i];
}
FOR(i,n-1){
int a,b;
cin>>a>>b;
g[a].ad(b);
g[b].ad(a);
}
decomp(1);
cout<<ans<<endl;
return 0;
}
Compilation message
zagrade.cpp: In function 'void decomp(int)':
zagrade.cpp:8:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define FOR(i,a) for (int i=0;i<(a);++i)
^
zagrade.cpp:107:5: note: in expansion of macro 'FOR'
FOR(i,g[cent].size()){
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
9720 KB |
Output is correct |
| 2 |
Correct |
12 ms |
9720 KB |
Output is correct |
| 3 |
Correct |
12 ms |
9720 KB |
Output is correct |
| 4 |
Correct |
12 ms |
9720 KB |
Output is correct |
| 5 |
Correct |
11 ms |
9724 KB |
Output is correct |
| 6 |
Correct |
12 ms |
9848 KB |
Output is correct |
| 7 |
Correct |
12 ms |
9828 KB |
Output is correct |
| 8 |
Correct |
11 ms |
9720 KB |
Output is correct |
| 9 |
Correct |
12 ms |
9720 KB |
Output is correct |
| 10 |
Correct |
10 ms |
9720 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
715 ms |
39784 KB |
Output is correct |
| 2 |
Correct |
599 ms |
40236 KB |
Output is correct |
| 3 |
Correct |
736 ms |
39896 KB |
Output is correct |
| 4 |
Correct |
626 ms |
40180 KB |
Output is correct |
| 5 |
Correct |
738 ms |
39732 KB |
Output is correct |
| 6 |
Correct |
993 ms |
40956 KB |
Output is correct |
| 7 |
Correct |
746 ms |
39848 KB |
Output is correct |
| 8 |
Correct |
1000 ms |
40836 KB |
Output is correct |
| 9 |
Correct |
717 ms |
39676 KB |
Output is correct |
| 10 |
Correct |
1480 ms |
47628 KB |
Output is correct |
| 11 |
Incorrect |
779 ms |
40180 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
9720 KB |
Output is correct |
| 2 |
Correct |
12 ms |
9720 KB |
Output is correct |
| 3 |
Correct |
12 ms |
9720 KB |
Output is correct |
| 4 |
Correct |
12 ms |
9720 KB |
Output is correct |
| 5 |
Correct |
11 ms |
9724 KB |
Output is correct |
| 6 |
Correct |
12 ms |
9848 KB |
Output is correct |
| 7 |
Correct |
12 ms |
9828 KB |
Output is correct |
| 8 |
Correct |
11 ms |
9720 KB |
Output is correct |
| 9 |
Correct |
12 ms |
9720 KB |
Output is correct |
| 10 |
Correct |
10 ms |
9720 KB |
Output is correct |
| 11 |
Correct |
715 ms |
39784 KB |
Output is correct |
| 12 |
Correct |
599 ms |
40236 KB |
Output is correct |
| 13 |
Correct |
736 ms |
39896 KB |
Output is correct |
| 14 |
Correct |
626 ms |
40180 KB |
Output is correct |
| 15 |
Correct |
738 ms |
39732 KB |
Output is correct |
| 16 |
Correct |
993 ms |
40956 KB |
Output is correct |
| 17 |
Correct |
746 ms |
39848 KB |
Output is correct |
| 18 |
Correct |
1000 ms |
40836 KB |
Output is correct |
| 19 |
Correct |
717 ms |
39676 KB |
Output is correct |
| 20 |
Correct |
1480 ms |
47628 KB |
Output is correct |
| 21 |
Incorrect |
779 ms |
40180 KB |
Output isn't correct |
