oj.uz

Submission #13587

# Submission time Handle Problem Language Result Execution time Memory
13587 2015-02-25T04:08:12 Z gs14004 Shymbulak (IZhO14_shymbulak) C++14
89.67 / 100
 152 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;
    }
    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
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 14092 KB Output is correct
2 Correct 0 ms 14092 KB Output is correct
3 Correct 0 ms 14092 KB Output is correct
4 Correct 0 ms 14092 KB Output is correct
5 Correct 3 ms 14092 KB Output is correct
6 Correct 0 ms 14092 KB Output is correct
7 Correct 0 ms 14092 KB Output is correct
8 Correct 0 ms 14092 KB Output is correct
9 Correct 0 ms 14092 KB Output is correct
10 Correct 0 ms 14092 KB Output is correct
11 Correct 0 ms 14092 KB Output is correct
12 Correct 0 ms 14092 KB Output is correct
13 Correct 0 ms 14092 KB Output is correct
14 Correct 0 ms 14092 KB Output is correct
15 Correct 4 ms 14092 KB Output is correct

Subtask #2
18.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14092 KB Output is correct
2 Correct 0 ms 14092 KB Output is correct
3 Correct 2 ms 14092 KB Output is correct
4 Correct 2 ms 14092 KB Output is correct
5 Correct 3 ms 14224 KB Output is correct
6 Correct 0 ms 14404 KB Output is correct
7 Correct 0 ms 14224 KB Output is correct
8 Incorrect 3 ms 14224 KB Output isn't correct
9 Correct 7 ms 14224 KB Output is correct
10 Correct 6 ms 14224 KB Output is correct

Subtask #3
41.667 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 17256 KB Output is correct
2 Incorrect 75 ms 17652 KB Output isn't correct
3 Correct 76 ms 19328 KB Output is correct
4 Correct 55 ms 17388 KB Output is correct
5 Correct 56 ms 17520 KB Output is correct
6 Correct 152 ms 20028 KB Output is correct
7 Incorrect 121 ms 19172 KB Output isn't correct
8 Correct 117 ms 20820 KB Output is correct
9 Correct 129 ms 20820 KB Output is correct
10 Correct 110 ms 21216 KB Output is correct
11 Correct 126 ms 27208 KB Output is correct
12 Correct 132 ms 27520 KB Output is correct