oj.uz

Submission #26300

# Submission time Handle Problem Language Result Execution time Memory
26300 2017-06-29T06:01:22 Z 시제연(#1104) Zagrade (COI17_zagrade) C++
0 / 100
 436 ms 48752 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;j<=ssz;j++) {
                res += top[j+bias]*scl[1-j+bias];
                res += sop[j+bias]*tcl[1-j+bias];
            }
        }
        else {
            for (j=-ssz;j<=ssz;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;
        }
    }
    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);
    }
}

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:99: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:111:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
                   ^
zagrade.cpp:112:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s",bra);
                    ^
zagrade.cpp:116: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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 22924 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 436 ms 48752 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 22924 KB Output isn't correct
2 Halted 0 ms 0 KB -