oj.uz

Submission #13907

# Submission time Handle Problem Language Result Execution time Memory
13907 2015-04-22T07:12:42 Z Namnamseo Shymbulak (IZhO14_shymbulak) C++
98 / 100
 129 ms 21336 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) {
        ans=max(ans,make_pair(ret.first+smax.first+1,ret.second*smax.second));
    }
    if(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) /*printf("Cyc %d\n",cycstack[i]),*/depth[i]=depth[cycind+i]=findDepth(cycstack[i]);
    t=1+cycind/2;
    for(i=0;i<t-1;++i) mi[depth[i].first-i]+=depth[i].second;
    map<int,long long>::iterator it;
    pli tmp;
    //for(i=0;i<2*cycind;++i) printf("%2d ",getPlus (i)); putchar(10);
    //for(i=0;i<2*cycind;++i) printf("%2d ",getMinus(i)); putchar(10);
    ////for(i=0;i<2*cycind;++i) printf("%2d ",depth[i].first ); putchar(10);
    //for(i=0;i<2*cycind;++i) printf("%2d ",depth[i].second); putchar(10);
    //printf("first %d %d\n",ans.first,ans.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
28.0 / 30.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14104 KB Output is correct
2 Correct 0 ms 14104 KB Output is correct
3 Correct 4 ms 14104 KB Output is correct
4 Correct 4 ms 14104 KB Output is correct
5 Correct 0 ms 14236 KB Output is correct
6 Correct 2 ms 14236 KB Output is correct
7 Correct 6 ms 14236 KB Output is correct
8 Correct 3 ms 14236 KB Output is correct
9 Correct 0 ms 14236 KB Output is correct
10 Correct 2 ms 14236 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 17008 KB Output is correct
2 Correct 55 ms 17404 KB Output is correct
3 Correct 68 ms 20548 KB Output is correct
4 Correct 46 ms 17272 KB Output is correct
5 Correct 35 ms 17272 KB Output is correct
6 Correct 88 ms 19648 KB Output is correct
7 Correct 87 ms 18724 KB Output is correct
8 Correct 95 ms 20440 KB Output is correct
9 Correct 129 ms 20440 KB Output is correct
10 Correct 63 ms 20948 KB Output is correct
11 Correct 68 ms 21072 KB Output is correct
12 Correct 84 ms 21336 KB Output is correct