oj.uz

Submission #13910

# Submission time Handle Problem Language Result Execution time Memory
13910 2015-04-22T07:57:23 Z Namnamseo Shymbulak (IZhO14_shymbulak) C++
0 / 100
 3 ms 14100 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()
{
    freopen("D:\\code\\iamcoder\\20150421\\proba\\input\\i29.txt","r",stdin);
    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
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 14100 KB open (syscall #2) was called by the program (disallowed syscall)
2 Runtime error 0 ms 14100 KB open (syscall #2) was called by the program (disallowed syscall)
3 Runtime error 3 ms 14100 KB open (syscall #2) was called by the program (disallowed syscall)
4 Runtime error 0 ms 14100 KB open (syscall #2) was called by the program (disallowed syscall)
5 Runtime error 0 ms 14100 KB open (syscall #2) was called by the program (disallowed syscall)
6 Runtime error 0 ms 14100 KB open (syscall #2) was called by the program (disallowed syscall)
7 Runtime error 0 ms 14100 KB open (syscall #2) was called by the program (disallowed syscall)
8 Runtime error 3 ms 14100 KB open (syscall #2) was called by the program (disallowed syscall)
9 Runtime error 3 ms 14100 KB open (syscall #2) was called by the program (disallowed syscall)
10 Runtime error 0 ms 14100 KB open (syscall #2) was called by the program (disallowed syscall)
11 Runtime error 3 ms 14100 KB open (syscall #2) was called by the program (disallowed syscall)
12 Runtime error 0 ms 14100 KB open (syscall #2) was called by the program (disallowed syscall)
13 Runtime error 0 ms 14100 KB open (syscall #2) was called by the program (disallowed syscall)
14 Runtime error 0 ms 14100 KB open (syscall #2) was called by the program (disallowed syscall)
15 Runtime error 0 ms 14100 KB open (syscall #2) was called by the program (disallowed syscall)

Subtask #2
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 14100 KB open (syscall #2) was called by the program (disallowed syscall)
2 Runtime error 0 ms 14100 KB open (syscall #2) was called by the program (disallowed syscall)
3 Runtime error 0 ms 14100 KB open (syscall #2) was called by the program (disallowed syscall)
4 Runtime error 0 ms 14100 KB open (syscall #2) was called by the program (disallowed syscall)
5 Runtime error 0 ms 14100 KB open (syscall #2) was called by the program (disallowed syscall)
6 Runtime error 0 ms 14100 KB open (syscall #2) was called by the program (disallowed syscall)
7 Runtime error 0 ms 14100 KB open (syscall #2) was called by the program (disallowed syscall)
8 Runtime error 3 ms 14100 KB open (syscall #2) was called by the program (disallowed syscall)
9 Runtime error 0 ms 14100 KB open (syscall #2) was called by the program (disallowed syscall)
10 Runtime error 0 ms 14100 KB open (syscall #2) was called by the program (disallowed syscall)

Subtask #3
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 14100 KB open (syscall #2) was called by the program (disallowed syscall)
2 Runtime error 0 ms 14100 KB open (syscall #2) was called by the program (disallowed syscall)
3 Runtime error 3 ms 14100 KB open (syscall #2) was called by the program (disallowed syscall)
4 Runtime error 0 ms 14100 KB open (syscall #2) was called by the program (disallowed syscall)
5 Runtime error 0 ms 14100 KB open (syscall #2) was called by the program (disallowed syscall)
6 Runtime error 0 ms 14100 KB open (syscall #2) was called by the program (disallowed syscall)
7 Runtime error 3 ms 14100 KB open (syscall #2) was called by the program (disallowed syscall)
8 Runtime error 3 ms 14100 KB open (syscall #2) was called by the program (disallowed syscall)
9 Runtime error 0 ms 14100 KB open (syscall #2) was called by the program (disallowed syscall)
10 Runtime error 0 ms 14100 KB open (syscall #2) was called by the program (disallowed syscall)
11 Runtime error 3 ms 14100 KB open (syscall #2) was called by the program (disallowed syscall)
12 Runtime error 0 ms 14100 KB open (syscall #2) was called by the program (disallowed syscall)