oj.uz

답안 #13581

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
13581 2015-02-25T00:26:40 Z gs14004 관광지 (IZhO14_shymbulak) C++14
95.83 / 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[i] = t;
            freq[t.first] += t.second;
        }
    }
    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 == piv - 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,piv-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;
        }
    }
}

Subtask #1
30.0 / 30.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
45.833 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 76 ms 17248 KB Output is correct
2 Correct 76 ms 17644 KB Output is correct
3 Execution timed out 1500 ms 17248 KB Program timed out
4 Correct 58 ms 17380 KB Output is correct
5 Correct 70 ms 17512 KB Output is correct
6 Correct 158 ms 20020 KB Output is correct
7 Correct 111 ms 19164 KB Output is correct
8 Correct 130 ms 20812 KB Output is correct
9 Correct 143 ms 20812 KB Output is correct
10 Correct 212 ms 21208 KB Output is correct
11 Correct 148 ms 27200 KB Output is correct
12 Correct 154 ms 27512 KB Output is correct