oj.uz

Submission #13905

# Submission time Handle Problem Language Result Execution time Memory
13905 2015-04-22T07:08:30 Z Namnamseo Shymbulak (IZhO14_shymbulak) C++
89.67 / 100
 123 ms 18212 KB 
#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.0 / 30.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
41.667 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 13884 KB Output is correct
2 Correct 71 ms 14280 KB Output is correct
3 Correct 55 ms 17028 KB Output is correct
4 Correct 45 ms 14148 KB Output is correct
5 Correct 40 ms 14148 KB Output is correct
6 Correct 123 ms 16524 KB Output is correct
7 Correct 91 ms 15600 KB Output is correct
8 Correct 115 ms 17316 KB Output is correct
9 Correct 96 ms 17316 KB Output is correct
10 Correct 114 ms 17824 KB Output is correct
11 Incorrect 98 ms 17948 KB Output isn't correct
12 Incorrect 107 ms 18212 KB Output isn't correct