oj.uz

답안 #13572

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
13572 2015-02-24T14:10:26 Z gs14004 관광지 (IZhO14_shymbulak) C++14
12.33 / 100
 1500 ms 27512 KB 
#include <cstdio>
#include <vector>
#include <algorithm>
#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]){
            pi t = f(i,0);
            cycle_ret[get_cycle[i]] = t;
            freq[t.first] += t.second;
        }
    }
    for (int i=1; i<=piv; i++) {
        for (int j=i+1; j<=piv; j++) {
            if(j <= piv / 2 + i){
                int lng = cycle_ret[i].first + cycle_ret[j].first + j - i;
                freq[lng] += cycle_ret[i].second * cycle_ret[j].second;
            }
            if(j >= piv / 2 + i){
                int lng = cycle_ret[i].first + cycle_ret[j].first + piv - j + i;
                freq[lng] += cycle_ret[i].second * cycle_ret[j].second;
            }
        }
    }
    for (int i=n; i; i--) {
        if(freq[i]){
            printf("%lld",freq[i]);
            return 0;
        }
    }
}

Subtask #1
2.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 14084 KB Output is correct
2 Incorrect 0 ms 14084 KB Output isn't correct
3 Incorrect 0 ms 14084 KB Output isn't correct
4 Incorrect 3 ms 14084 KB Output isn't correct
5 Incorrect 0 ms 14084 KB Output isn't correct
6 Incorrect 3 ms 14084 KB Output isn't correct
7 Incorrect 0 ms 14084 KB Output isn't correct
8 Incorrect 3 ms 14084 KB Output isn't correct
9 Incorrect 0 ms 14084 KB Output isn't correct
10 Incorrect 0 ms 14084 KB Output isn't correct
11 Incorrect 0 ms 14084 KB Output isn't correct
12 Incorrect 0 ms 14084 KB Output isn't correct
13 Incorrect 3 ms 14084 KB Output isn't correct
14 Incorrect 0 ms 14084 KB Output isn't correct
15 Incorrect 0 ms 14084 KB Output isn't correct

Subtask #2
2.0 / 20.0

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

Subtask #3
8.333 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 57 ms 17248 KB Output is correct
2 Incorrect 78 ms 17644 KB Output isn't correct
3 Execution timed out 1500 ms 17248 KB Program timed out
4 Incorrect 60 ms 17380 KB Output isn't correct
5 Incorrect 61 ms 17512 KB Output isn't correct
6 Correct 159 ms 20020 KB Output is correct
7 Incorrect 118 ms 19164 KB Output isn't correct
8 Incorrect 134 ms 20812 KB Output isn't correct
9 Incorrect 129 ms 20812 KB Output isn't correct
10 Incorrect 169 ms 21208 KB Output isn't correct
11 Incorrect 118 ms 27200 KB Output isn't correct
12 Incorrect 151 ms 27512 KB Output isn't correct