Submission #13567

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
13567	2015-02-24T13:30:08 Z	gs14004	Shymbulak (IZhO14_shymbulak)	C++14	Compilation error	0 ms	0 KB

shymbulak

#include <cstdio>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
typedef long long lint;
typedef pair<int,lint> pi;

int n;

vector<int> graph[200005];
int deg[200005];

int piv;
int cycle_num[200005];
int get_cycle[200005];
int vis[200005];
pi cycle_ret[200005];

long long freq[200005];

void label_graph(){
    queue<int> q;
    for (int i=1; i<=n; i++) {
        if(deg[i] == 1){
            q.push(i);
        }
    }
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        deg[x] = 0;
        for (int &i : graph[x]){
            if(deg[i]){
                deg[i]--;
                if(deg[i] == 1){
                    q.push(i);
                }
            }
        }
    }
    for (int i=1; i<=n; i++) {
        if(deg[i]){
            q.push(i);
            break;
        }
    }
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        cycle_num[x] = ++piv;
        get_cycle[cycle_num[x]] = x;
        for (int &i : graph[x]){
            if(deg[i] && !cycle_num[i]){
                q.push(i);
                break;
            }
        }
    }
    for (int i=1; i<=n; i++) {
        if(cycle_num[i]){
            q.push(i);
            vis[i] = 1;
            while (!q.empty()) {
                int x = q.front();
                q.pop();
                for (int &i : graph[x]){
                    if(!vis[i]){
                        vis[i] = 1;
                        q.push(i);
                    }
                }
            }
        }
    }
}

bool cmp(pi a, pi b){
    return a.first > b.first;
}

pi f(int x, int pa){
    vector<pi> sub;
    for (int &i : graph[x]){
        if(i == pa) continue;
        if(cycle_num[i]) continue;
        pi t = f(i,x);
        t.first++;
        sub.push_back(t);
    }
    sort(sub.begin(),sub.end(),cmp);
    if(sub.size() == 0) return pi(0,1);
    if(sub.size() == 1){
        freq[sub[0].first] += sub[0].second;
        return sub[0];
    }
    if(sub[0].first == sub[1].first){
        pi t(sub[0].first,0);
        for (int i=0; i<sub.size(); i++) {
            if(sub[0].first == sub[i].first) t.second += sub[i].second;
        }
        long long sum = 1ll * t.second * t.second;
        for (int i=0; i<sub.size(); i++) {
            if(sub[0].first == sub[i].first) sum -= 1ll * sub[i].second * sub[i].second;
        }
        sum /= 2;
        freq[t.first * 2] += sum;
        return t;
    }
    int low_sub = 0;
    for (int i=1; i<sub.size(); i++) {
        if(sub[1].first == sub[i].first) low_sub += sub[i].second;
    }
    freq[sub[0].first + sub[1].first] += 1ll * low_sub * sub[0].second;
    return sub[0];
}

int main(){
    scanf("%d",&n);
    for (int i=0; i<n; i++) {
        int s,e;
        scanf("%d %d",&s,&e);
        graph[s].push_back(e);
        graph[e].push_back(s);
        deg[s]++;
        deg[e]++;
    }
    label_graph();
    for (int i=1; i<=n; i++) {
        if(cycle_num[i]){
            cycle_ret[i] = f(i,0);
        }
    }
    for (int i=1; i<=piv; i++) {
        for (int j=i+1; j<=piv; j++) {
            int pi = get_cycle[i], pj = get_cycle[j];
            if(j-i == n - j + i){
                int lng = cycle_ret[pi].first + cycle_ret[pj].first + j - i;
                freq[lng] += cycle_ret[pi].second * cycle_ret[pj].second * 2ll;
            }
            else{
                int lng = cycle_ret[pi].first + cycle_ret[pj].first + min(j-i,n-j+i);
                freq[lng] += cycle_ret[pi].second * cycle_ret[pj].second;
            }
        }
    }
    for (int i=n; i; i--) {
        if(freq[i]){
            printf("%lld",freq[i]);
            return 0;
        }
    }
}

Compilation message

shymbulak.cpp: In function ‘pi f(int, int)’:
shymbulak.cpp:91:35: error: ‘sort’ was not declared in this scope
     sort(sub.begin(),sub.end(),cmp);
                                   ^
shymbulak.cpp:99:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i=0; i<sub.size(); i++) {
                        ^
shymbulak.cpp:103:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i=0; i<sub.size(); i++) {
                        ^
shymbulak.cpp:111:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=1; i<sub.size(); i++) {
                    ^
shymbulak.cpp: In function ‘int main()’:
shymbulak.cpp:119:19: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
                   ^
shymbulak.cpp:122:29: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d",&s,&e);
                             ^