oj.uz

Submission #26307

# Submission time Handle Problem Language Result Execution time Memory
26307 2017-06-29T06:19:16 Z 시제연(#1104) Zagrade (COI17_zagrade) C++
100 / 100
 903 ms 47556 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n;
char bra[300100];
int pm[300100]; // -1, 1
vector<int> lis[300100];
bool dead[300100];
int sz[300100];
int bias = 160001;
ll sop[350000], scl[350000];
ll top[350000], tcl[350000];
ll res;

int idfs(int here, int p) {
    int i;
    sz[here] = 1;
    for (i=0;i<lis[here].size();i++) {
        int there = lis[here][i];
        if (there==p||dead[there]) continue;
        sz[here]+=idfs(there,here);
    }
    return sz[here];
}

int cdfs(int here, int p, int asz) {
    int i, maxi = 0, t = -1;
    for (i=0;i<lis[here].size();i++) {
        int there = lis[here][i];
        if (there==p||dead[there]) continue;
        if (maxi<sz[there]) {
            maxi = sz[there];
            t = there;
        }
    }
    if (maxi<=asz/2) return here;
    return cdfs(t,here,asz);
}

int findcen(int head) {
    return cdfs(head,-1,idfs(head,-1));
}

stack<int> mins, maxs;
void adfs(int here, int p, int val) {
    int i;
    val += pm[here];
    sz[here] = 1;
    if (mins.top()>=val) top[val+bias]++;
    if (maxs.top()<=val) tcl[val+bias]++;
    mins.push(min(mins.top(),val));
    maxs.push(max(maxs.top(),val));
    for (i=0;i<lis[here].size();i++) {
        int there = lis[here][i];
        if (there==p||dead[there]) continue;
        adfs(there,here,val);
        sz[here] += sz[there];
    }
    mins.pop(); maxs.pop();
}

void dnc(int head) {
    int cen = findcen(head), i, j;
    int asz = sz[head];
    mins.push(0); maxs.push(0);
    for (i=0;i<lis[cen].size();i++) {
        int there = lis[cen][i];
        if (dead[there]) continue;
        adfs(there,cen,0);
        int ssz = sz[there];
        if (pm[cen]==1) res += top[-1+bias];
        else res += tcl[1+bias];
        if (pm[cen]==-1) {
            for (j=-ssz-1;j<=ssz+1;j++) {
                res += top[j+bias]*scl[1-j+bias];
                res += sop[j+bias]*tcl[1-j+bias];
            }
        }
        else {
            for (j=-ssz-1;j<=ssz+1;j++) {
                res += top[j+bias]*scl[-1-j+bias];
                res += sop[j+bias]*tcl[-1-j+bias];
            }
        }
        for (j=-ssz;j<=ssz;j++) {
            sop[j+bias] += top[j+bias];
            top[j+bias] = 0;
            scl[j+bias] += tcl[j+bias];
            tcl[j+bias] = 0;
        }
    }
    mins.pop(); maxs.pop();
    for (j=-asz;j<=asz;j++) {
        sop[j+bias] = scl[j+bias] = 0;
    }
    dead[cen] = true;
    for (i=0;i<lis[cen].size();i++) {
        int there = lis[cen][i];
        if (dead[there]) continue;
        dnc(there);
    }
}

bool good(int i, int j) {
    if (i==j) return false;
    int st = ((i<j)?1:-1), sum = 0;
    for (int p=i;p!=j+st;p+=st) {
        sum += pm[p];
        if (sum>0) return false;
    }
    return sum==0;
}

int main() {
    int i;

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

    scanf("%d",&n);
    scanf("%s",bra);
    for (i=0;i<n;i++) pm[i] = ((bra[i]==')')?1:-1);
    for (i=0;i<n-1;i++) {
        int a, b;
        scanf("%d%d",&a,&b);
        a--;b--;
        lis[a].push_back(b);
        lis[b].push_back(a);
    }
    dnc(0);
    printf("%lld\n",res);

    return 0;
}

Compilation message

zagrade.cpp: In function 'int idfs(int, int)':
zagrade.cpp:21:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<lis[here].size();i++) {
               ^
zagrade.cpp: In function 'int cdfs(int, int, int)':
zagrade.cpp:31:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<lis[here].size();i++) {
               ^
zagrade.cpp: In function 'void adfs(int, int, int)':
zagrade.cpp:56:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<lis[here].size();i++) {
               ^
zagrade.cpp: In function 'void dnc(int)':
zagrade.cpp:69:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<lis[cen].size();i++) {
               ^
zagrade.cpp:100:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<lis[cen].size();i++) {
               ^
zagrade.cpp: In function 'int main()':
zagrade.cpp:122:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
                   ^
zagrade.cpp:123:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s",bra);
                    ^
zagrade.cpp:127:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&a,&b);
                            ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 22924 KB Output is correct
2 Correct 0 ms 22924 KB Output is correct
3 Correct 0 ms 22924 KB Output is correct
4 Correct 3 ms 22924 KB Output is correct
5 Correct 3 ms 22924 KB Output is correct
6 Correct 3 ms 22924 KB Output is correct
7 Correct 0 ms 22924 KB Output is correct
8 Correct 0 ms 22924 KB Output is correct
9 Correct 6 ms 22924 KB Output is correct
10 Correct 6 ms 22924 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 423 ms 47552 KB Output is correct
2 Correct 409 ms 47552 KB Output is correct
3 Correct 469 ms 47552 KB Output is correct
4 Correct 416 ms 47548 KB Output is correct
5 Correct 423 ms 47552 KB Output is correct
6 Correct 416 ms 47548 KB Output is correct
7 Correct 393 ms 47556 KB Output is correct
8 Correct 429 ms 47556 KB Output is correct
9 Correct 413 ms 47556 KB Output is correct
10 Correct 409 ms 47556 KB Output is correct
11 Correct 419 ms 47552 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 22924 KB Output is correct
2 Correct 0 ms 22924 KB Output is correct
3 Correct 0 ms 22924 KB Output is correct
4 Correct 3 ms 22924 KB Output is correct
5 Correct 3 ms 22924 KB Output is correct
6 Correct 3 ms 22924 KB Output is correct
7 Correct 0 ms 22924 KB Output is correct
8 Correct 0 ms 22924 KB Output is correct
9 Correct 6 ms 22924 KB Output is correct
10 Correct 6 ms 22924 KB Output is correct
11 Correct 423 ms 47552 KB Output is correct
12 Correct 409 ms 47552 KB Output is correct
13 Correct 469 ms 47552 KB Output is correct
14 Correct 416 ms 47548 KB Output is correct
15 Correct 423 ms 47552 KB Output is correct
16 Correct 416 ms 47548 KB Output is correct
17 Correct 393 ms 47556 KB Output is correct
18 Correct 429 ms 47556 KB Output is correct
19 Correct 413 ms 47556 KB Output is correct
20 Correct 409 ms 47556 KB Output is correct
21 Correct 419 ms 47552 KB Output is correct
22 Correct 899 ms 32692 KB Output is correct
23 Correct 903 ms 32692 KB Output is correct
24 Correct 759 ms 32692 KB Output is correct
25 Correct 806 ms 32692 KB Output is correct
26 Correct 406 ms 37332 KB Output is correct
27 Correct 513 ms 34988 KB Output is correct
28 Correct 526 ms 34188 KB Output is correct
29 Correct 389 ms 47556 KB Output is correct
30 Correct 443 ms 47556 KB Output is correct
31 Correct 136 ms 34408 KB Output is correct
32 Correct 419 ms 47552 KB Output is correct