IOI 2008 Island source code

Omnoh poston deer bichsen analyze-n daguu bichsen source-g postolloo. Latin-aar bichij bgad uuchlaarai, oor arga alga kk. Yag sonirhoj tsag gargaj suuj bga huuhded, asuuval, iluu, dutuu zuiluudiig tailbarlaj zaaj ogno. Tiimees source-nd ymr ch tailbar hiihgui.

#include <cstdio>
#include <cstdlib>
#define MaxN 500010
#define MaxM 1000020
#define LL long long
using namespace std;
int  N, M, Last[MaxN], Next[MaxN], Pre[MaxM];
int  spoint, Q[MaxM], Other[MaxM], Opp[MaxM], tNext[MaxM];
LL   Ans, Tot, Rec[MaxM], Dist[MaxM], Cost[MaxM], F[MaxN];  
char V[MaxN] = {0}, Col[MaxN] = {0};

void Gf1(int Now, int Fa) {
          int  y, k, m;  
          for (V[Now] = 1, y = Last[Now]; y != 0; y = Pre[y]) {
             k = Other[y];
             if (!V[k]) { 
                tNext[Now] = y; 
                Gf1(k, Opp[y]); 
              } else if(y != Fa && spoint == -1) {
                m = Now; tNext[Now] = y; spoint = Now; 
                do {
                    Col[m] = 1;
                    Next[m] = tNext[m];
                    m = Other[Next[m]];
                } while (m != Now); 
             }
          }
}
      
void Gf2(int Now, int Fa) {
          int  y, k;  LL m, m1, m2;
          
          for (m = m1 = m2 = 0, y = Last[Now]; y != 0; y = Pre[y]) {
              k = Other[y];
              if (y != Fa && !Col[k]) {
                  Gf2(k, Opp[y]);  
                  m = F[k]+Cost[y];
                  if (m > m1) {
                    m2 = m1;
                    m1 = m;
                  } else if (m > m2) m2 = m;
              }              
          }
          F[Now] = m1;  
          if (Ans < m1+m2) 
            Ans = m1+m2;
}
            
int main() {
          LL v1, v2, Len;
          int i, k, x, t, h, Now; 
          freopen("in.txt", "r", stdin);
          freopen("out.txt", "w", stdout);
          for (scanf("%d", &N), k = 0, i = 1; i <= N;i ++) {
             scanf("%d %lld",&x, &Len);    
             Other[++k] = i; Cost[k] = Len; Opp[k] = k+1; Pre[k] = Last[x]; Last[x] = k;
             Other[++k] = x; Cost[k] = Len; Opp[k] = k-1; Pre[k] = Last[i]; Last[i] = k;
          }
          for (Tot = 0, k = 1; k <= N; k++) if (!V[k]) {           
              spoint = -1;  Gf1(k, -1);  Now = spoint; 
              Ans = 0; M = 0; t = 0; h = 0;
              do {
                M++; 
                Gf2(Now,-1); 
                Now = Other[Next[Now]];
              } while (Now!=spoint);  
                      
              for (Dist[1] = 0, i = 1; i < M+M ; i++) {
                    Dist[i+1] = Dist[i] + Cost[Next[Now]];  
                    Rec[i] = F[Now];  
                    v1 = Dist[i]+Rec[i];           
                    v2 = -Dist[i]+Rec[i];   
                    while (i-Q[h] >= M)
                      h++;
                    if (h > 0 && Ans < v1-Dist[Q[h]]+Rec[Q[h]]) 
                      Ans = v1 - Dist[Q[h]] + Rec[Q[h]];                    
                    while (t > 0 && t >= h && v2 > Rec[Q[t]]-Dist[Q[t]]) 
                      t--;  
                    
                    Now = Other[Next[Now]]; Q[++t] = i;
              }    
              Tot += Ans;
          }
          printf("%lld\n", Tot);  
          return 0;    
}