Submission #13905

#	Time	Username	Problem	Language	Result	Execution time	Memory
13905		Namnamseo	Shymbulak (IZhO14_shymbulak)	C++98	89.67 / 100	123 ms	18212 KiB

shymbulak

#include <cstdio>
#include <cassert>
#include <algorithm>
#include <vector>
#include <map>
#define maxn 200010
using namespace std;
typedef pair<int,int> pp;

bool    cycle[maxn];
bool  visited[maxn];
int    parent[maxn];
int  cycstack[maxn];
pp      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;
pp ans(0,1);

pp findDepth(int pos){
    visited[pos]=true;
    int i,s=edge[pos].size(),nxt;
    pp ret(0,1),smax(0,0);
    int max_tmp=0;
    for(i=0;i<s;++i){
        nxt=edge[pos][i];
        if(!visited[nxt] && !cycle[nxt]) {
            pp 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,int> 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,int>::iterator it;
    pp 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("%d\n",ans.second);
    return 0;
}

• Subtask 1: 28 / 30
• Subtask 2: 20 / 20
• Subtask 3: 41.667 / 50