oj.uz

답안 #13586

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
13586 2015-02-25T00:45:04 Z gs14004 관광지 (IZhO14_shymbulak) C++14
40.67 / 100
 165 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;
    }
    for (int i=n; i; i--) {
        if(freq[i]){
            printf("%lld",freq[i]);
            return 0;
        }
    }
}

Subtask #1
18.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 14092 KB Output isn't correct
2 Correct 3 ms 14092 KB Output is correct
3 Incorrect 0 ms 14092 KB Output isn't correct
4 Correct 3 ms 14092 KB Output is correct
5 Correct 0 ms 14092 KB Output is correct
6 Incorrect 0 ms 14092 KB Output isn't correct
7 Incorrect 1 ms 14092 KB Output isn't 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 Incorrect 3 ms 14092 KB Output isn't correct
13 Correct 3 ms 14092 KB Output is correct
14 Correct 0 ms 14092 KB Output is correct
15 Incorrect 0 ms 14092 KB Output isn't correct

Subtask #2
6.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 14092 KB Output isn't correct
2 Correct 0 ms 14092 KB Output is correct
3 Incorrect 2 ms 14092 KB Output isn't correct
4 Incorrect 4 ms 14092 KB Output isn't correct
5 Incorrect 0 ms 14224 KB Output isn't correct
6 Correct 0 ms 14404 KB Output is correct
7 Correct 0 ms 14224 KB Output is correct
8 Incorrect 0 ms 14224 KB Output isn't correct
9 Incorrect 6 ms 14224 KB Output isn't correct
10 Incorrect 3 ms 14224 KB Output isn't correct

Subtask #3
16.667 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 85 ms 17256 KB Output is correct
2 Incorrect 70 ms 17652 KB Output isn't correct
3 Incorrect 85 ms 19856 KB Output isn't correct
4 Incorrect 68 ms 17388 KB Output isn't correct
5 Incorrect 54 ms 17520 KB Output isn't correct
6 Correct 165 ms 20028 KB Output is correct
7 Incorrect 65 ms 19172 KB Output isn't correct
8 Incorrect 122 ms 20820 KB Output isn't correct
9 Incorrect 142 ms 20820 KB Output isn't correct
10 Incorrect 115 ms 21216 KB Output isn't correct
11 Correct 132 ms 27208 KB Output is correct
12 Correct 120 ms 27520 KB Output is correct