oj.uz

Submission #13588

# Submission time Handle Problem Language Result Execution time Memory
13588 2015-02-25T04:13:14 Z gs14004 Shymbulak (IZhO14_shymbulak) C++14
0 / 100
 160 ms 27520 KB 
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
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];
}

map<int,long long> mp;

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]){
            pi t = f(i,0);
            cycle_ret[cycle_num[i]] = t;
            freq[t.first] += t.second;
        }
    }
    for (int j=2; j<=piv/2; j++) {
        int lng = cycle_ret[j].first + j;
        mp[lng] += cycle_ret[j].second;
    }
    for (int i=1; i<=piv; i++) {
        if(i + piv/2 <= piv){
            int j = i + piv / 2;
            int lng = cycle_ret[j].first + j;
            mp[lng] += cycle_ret[j].second;
        }
        auto x = mp.rbegin();
        freq[cycle_ret[i].first - i + (x->first)] += (x -> second) * cycle_ret[i].second;
        int lng = cycle_ret[i+1].first + i+1;
        mp[lng] -= cycle_ret[i+1].second;
        if(mp[lng] == 0) mp.erase(lng);
    }
    mp.clear();
    for (int j=1 + (piv+1)/2; j<=piv; j++) {
        int lng = cycle_ret[j].first + piv - j;
        mp[lng] += cycle_ret[j].second;
    }
    for (int i=1; i<=piv && !mp.empty(); i++) {
        auto x = mp.rbegin();
        freq[cycle_ret[i].first + i + (x->first)] += (x->second) * cycle_ret[i].second;
        int j = i + (piv + 1)/2;
        int lng = cycle_ret[j].first + piv - j;
        mp[lng] -= cycle_ret[j].second;
        if(mp[lng] == 0) mp.erase(lng);
    }
    for (int i=n; i; i--) {
        if(freq[i]){
            printf("%lld",freq[i]);
            return 0;
        }
    }
}

Subtask #1
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 14088 KB SIGSEGV Segmentation fault
2 Runtime error 0 ms 14088 KB SIGSEGV Segmentation fault
3 Runtime error 0 ms 14088 KB SIGSEGV Segmentation fault
4 Runtime error 0 ms 14088 KB SIGSEGV Segmentation fault
5 Runtime error 0 ms 14088 KB SIGSEGV Segmentation fault
6 Runtime error 3 ms 14088 KB SIGSEGV Segmentation fault
7 Runtime error 0 ms 14088 KB SIGSEGV Segmentation fault
8 Runtime error 3 ms 14088 KB SIGSEGV Segmentation fault
9 Runtime error 0 ms 14088 KB SIGSEGV Segmentation fault
10 Runtime error 0 ms 14088 KB SIGSEGV Segmentation fault
11 Runtime error 0 ms 14088 KB SIGSEGV Segmentation fault
12 Runtime error 0 ms 14088 KB SIGSEGV Segmentation fault
13 Runtime error 0 ms 14088 KB SIGSEGV Segmentation fault
14 Runtime error 0 ms 14088 KB SIGSEGV Segmentation fault
15 Runtime error 0 ms 14088 KB SIGSEGV Segmentation fault

Subtask #2
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 14088 KB SIGSEGV Segmentation fault
2 Runtime error 0 ms 14088 KB SIGSEGV Segmentation fault
3 Runtime error 3 ms 14088 KB SIGSEGV Segmentation fault
4 Runtime error 0 ms 14088 KB SIGSEGV Segmentation fault
5 Runtime error 0 ms 14220 KB SIGSEGV Segmentation fault
6 Runtime error 0 ms 14404 KB SIGSEGV Segmentation fault
7 Runtime error 4 ms 14220 KB SIGSEGV Segmentation fault
8 Runtime error 0 ms 14220 KB SIGSEGV Segmentation fault
9 Runtime error 0 ms 14220 KB SIGSEGV Segmentation fault
10 Runtime error 3 ms 14220 KB SIGSEGV Segmentation fault

Subtask #3
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Runtime error 44 ms 17256 KB SIGSEGV Segmentation fault
2 Runtime error 77 ms 17652 KB SIGSEGV Segmentation fault
3 Runtime error 65 ms 18268 KB SIGSEGV Segmentation fault
4 Runtime error 54 ms 17388 KB SIGSEGV Segmentation fault
5 Runtime error 60 ms 17520 KB SIGSEGV Segmentation fault
6 Runtime error 160 ms 20028 KB SIGSEGV Segmentation fault
7 Runtime error 108 ms 19172 KB SIGSEGV Segmentation fault
8 Runtime error 106 ms 20820 KB SIGSEGV Segmentation fault
9 Runtime error 123 ms 20820 KB SIGSEGV Segmentation fault
10 Runtime error 100 ms 21216 KB SIGSEGV Segmentation fault
11 Runtime error 105 ms 27208 KB SIGSEGV Segmentation fault
12 Runtime error 108 ms 27520 KB SIGSEGV Segmentation fault