oj.uz

답안 #13911

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
13911 2015-04-22T07:57:45 Z Namnamseo 관광지 (IZhO14_shymbulak) C++
77.33 / 100
 133 ms 21340 KB 
#include <cstdio>
#include <cassert>
#include <algorithm>
#include <vector>
#include <map>
#define maxn 200010
using namespace std;
typedef pair<int,long long> pli;

bool    cycle[maxn];
bool  visited[maxn];
int    parent[maxn];
int  cycstack[maxn];
pli     depth[maxn*2];
int  cycind;

vector<int> edge[maxn];

int cyclepeak;

void dfs(int pos){
    visited[pos]=true;
    int i,s=edge[pos].size(),nxt;
    for(i=0;i<s;++i){
        nxt=edge[pos][i];
        if(parent[pos]!=nxt){
            if(visited[nxt]){
                if(cycind) continue;
                int tmp=pos;
                for(;;){
                    cycle[tmp]=true;
                    cycstack[cycind++]=tmp;
                    if(tmp==nxt) break;
                    tmp=parent[tmp];
                }
                cyclepeak=nxt;
            } else {
                parent[nxt]=pos;
                dfs(nxt);
            }
        }
    }
}

int n;
pli ans(0,1);

pli findDepth(int pos){
    visited[pos]=true;
    int i,s=edge[pos].size(),nxt;
    pli ret(0,1),smax(0,0);
    long long max_tmp=0;
    for(i=0;i<s;++i){
        nxt=edge[pos][i];
        if(!visited[nxt] && !cycle[nxt]) {
            pli tmp = findDepth(nxt);
            ++tmp.first;
            if(ret.first < tmp.first){
                smax=ret;
                ret=tmp;
                max_tmp=0;
            } else if(ret.first == tmp.first){
                max_tmp += ret.second*tmp.second;
                ret.second+=tmp.second;
            } else {
                if(smax.first==tmp.first) smax.second+=tmp.second;
                else if(smax<tmp) smax=tmp;
            }
        }
    }
    if(ret.second && smax.first && smax.second) {
        if(ret.first+smax.first+1 == ans.first) ans.second+=ret.second*smax.second;
        ans=max(ans,make_pair(ret.first+smax.first+1,ret.second*smax.second));
    }
    if(max_tmp) {
        if(ans.first==ret.first*2+1) ans.second+=max_tmp;
        ans=max(ans,make_pair(ret.first*2+1,max_tmp));
    }
    return ret;
}

map<int,long long> mi;

int getPlus (int x) { return depth[x].first+x; }
int getMinus(int x) { return depth[x].first-x; }

int main()
{
    scanf("%d",&n);
    int i,t,a,b;
    for(i=1;i<=n;++i) scanf("%d%d",&a,&b),edge[a].push_back(b), edge[b].push_back(a);
    parent[1]=-1;
    dfs(1);
    for(i=1;i<=n;++i) visited[i]=false;
    for(i=0;i<cycind;++i) depth[i]=depth[cycind+i]=findDepth(cycstack[i]);
    t=1+cycind/2;
    pli tmp;
    map<int,long long>::iterator it;
    for(i=0;i<t-1;++i) {
        if(i!=0){
            it=mi.end(); --it;
            tmp.first=1+getPlus(i)+it->first;
            tmp.second=depth[i].second*it->second;
            if(ans.first==tmp.first) ans.second+=tmp.second;
            else if(ans.first<tmp.first) ans=tmp;
        }
        mi[depth[i].first-i]+=depth[i].second;
    }
    for(i=t-1;i<=cycind+t-2;++i){
        it=mi.end(); --it;
        tmp.first =1+getPlus(i)+it->first;
        tmp.second=depth[i].second*it->second;
        //printf("Plus %d cnt %d, Minus val %d cnt %d\n",getPlus(i),depth[i].second,it->first,it->second);
        if(ans.first==tmp.first) ans.second+=tmp.second;
        else if(ans.first<tmp.first) ans=tmp;
        a=i-t+1;
        mi[getMinus(a)]-=depth[a].second;
        if(mi[getMinus(a)]==0) mi.erase(getMinus(a));
        mi[getMinus(i)]+=depth[i].second; 
    }
    printf("%lld\n",ans.second);
    return 0;
}

Subtask #1
30.0 / 30.0

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

Subtask #2
14.0 / 20.0

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

Subtask #3
33.333 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 65 ms 17012 KB Output is correct
2 Correct 53 ms 17408 KB Output is correct
3 Correct 67 ms 20552 KB Output is correct
4 Incorrect 57 ms 17276 KB Output isn't correct
5 Incorrect 28 ms 17276 KB Output isn't correct
6 Correct 133 ms 19652 KB Output is correct
7 Correct 103 ms 18728 KB Output is correct
8 Incorrect 121 ms 20444 KB Output isn't correct
9 Incorrect 100 ms 20444 KB Output isn't correct
10 Correct 98 ms 20948 KB Output is correct
11 Correct 90 ms 21076 KB Output is correct
12 Correct 125 ms 21340 KB Output is correct