Submission #45176

#	Time	Username	Problem	Language	Result	Execution time	Memory
45176		rajarshi_basu	Shymbulak (IZhO14_shymbulak)	C++14	0 / 100	141 ms	12824 KiB

shymbulak

#include <iostream>
#include <algorithm>
#include <stack>
#include <string>
#include <stdio.h>
#include <cmath>
#include <queue>
#include <functional>


#define FOR(i,n) for(int i=0;i<n;i++)
#define FORE(i,a,b) for(int i=a;i<=b;i++)
#define ll long long int
#define pb(a) push_back(a)
#define vi vector<int>
#define ii pair<int,int>
#define iii pair<bool, pair<int,int> >
#define mp(a,b) make_pair(a,b)

struct Edge{
  int a;int b;
  int ind;
  bool bad;
};

using namespace std;

vector<Edge*>* g;
int n;
Edge** edges;
bool* sp_node;
bool* sp_edge;
bool* visited;
int ancestor = -1;
bool ex = false;
int IND__ = 0;
int* index_;

void dfs_cycle(int node,int p){
  visited[node] = true;
  FOR(i,g[node].size()){
    Edge* ed = g[node][i];
    int u = ed->a == node?ed->b:ed->a;
    if(u == p)continue;
    if(visited[u]){
      ancestor = u;
      if(ex)return;
      ed->bad = true;
      //ed->ind = IND__++;
      index_[node] = IND__++;
    }else{
      if(ex)return;
      dfs_cycle(u,node);
      if(ancestor != -1){
        if(ancestor == node){
          ed->bad = true;
          //ed->ind = IND__++;
          index_[node] = IND__++;
          ex = true;
        }
        if(ex)return;
        ed->bad = true;
        //ed->ind = IND__++;
        index_[node] = IND__++;
        return;
      }
    }
  }
}



ii maxDpthDFS(int node,int p){
  ii mx;
  mx.first = 0;mx.second = 1;
  FOR(i,g[node].size()){
    Edge* ed = g[node][i];
    int u = ed->a == node?ed->b:ed->a;
    if(u == p)continue;
    if(ed->bad)continue;
    ii val = maxDpthDFS(u,node);
    if(val.first > mx.first){
      mx.first = val.first;
      mx.second = val.second;
    }else if(val.first == mx.first){
      mx.second+=val.second;
    }
  }
  mx.first++;
  return mx;
}

int main(){
  cin >> n;
  g = new vector<Edge*>[n];
  index_= new int[n];
  FOR(i,n){
    index_[i] = -1;
  }
  edges = new Edge*[n];
  FOR(i,n){
    int a,b;
    cin >> a >> b;
    a--;
    b--;
    Edge* ed = new Edge();
    ed->a = a;
    ed->b = b;
    ed->bad = false;
    edges[i] = ed;
    g[a].pb(ed);
    g[b].pb(ed);
  }
  visited = new bool[n];
  FOR(i,n)visited[i] = false;
  dfs_cycle(0,-1);
  //cout << endl<<endl;
  //cout <<ancestor<<endl;
  //FOR(i,n){
  //  if(edges[i]->bad){
  //    cout << edges[i]->a +1<< "  " << edges[i]->b + 1<<endl;
  //  }
  //}
  sp_node = new bool[n];
  sp_edge = new bool[n];
  FOR(i,n)sp_node[i] = sp_edge[i] = false;
  FOR(i,n){
    if(edges[i]->bad){
      sp_node[edges[i]->a] = sp_node[edges[i]->b] = true;
      sp_edge[i] = true;
    }
  }
  //cout << "hell0" <<endl;
  ii vals[n];
  FOR(i,n)vals[i].first = vals[i].second = 0;
  FOR(i,n){
    if(sp_node[i])vals[i] = maxDpthDFS(i,-1);
  }
  //cout << IND__ <<endl;
  ii all[IND__*3];
  //IND__ = 0;
  FOR(i,n){
   // cout << edges[i]->a  << "  "<<edges[i]->b << "  " <<edges[i]->bad << " " <<edges[i]->ind<<endl;
  }
  FOR(i,n){
    if(sp_node[i]){
      all[index_[i]+IND__*2] = all[index_[i]+IND__] = all[index_[i]] = vals[i];
    }
  }
  /*
  FOR(i,n){
    cout << vals[i].first << " " << vals[i].second <<endl;
  }
  cout <<endl;
  FOR(i,3*IND__){
    cout << all[i].first << " "<<all[i].second <<endl;
  }*/

  int mx=0;int ctr=0;
  int cnt = IND__/2;
  //cout << "cnt : "<<cnt<<endl;
  FOR(i,IND__){
    int st = IND__ + i;
    i+=IND__;
    FORE(j,1,cnt){

      if(all[i].first + all[i+j].first + j-1 > mx){
        mx= all[i].first + all[i+j].first + j-1;
        ctr = all[i].second*all[i+j].second;
      }else if(all[i].first + all[i+j].first + j-1 == mx){
        ctr += all[i].second*all[i+j].second;
      }
      if(all[i].first + all[i-j].first + j-1 > mx){
        mx= all[i].first + all[i-j].first + j-1;
        ctr = all[i].second*all[i-j].second;
      }else if(all[i].first + all[i-j].first + j-1 == mx){
        ctr += all[i].second*all[i-j].second;
      }
    }
    //cout << mx << "    =----=    "<<ctr <<endl;
    i-=IND__;

  }
 // cout << mx <<endl;
  cout << ctr/2 <<endl;

  return 0;
}

Compilation message (stderr)

shymbulak.cpp: In function 'void dfs_cycle(int, int)':
shymbulak.cpp:11:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i,n) for(int i=0;i<n;i++)
shymbulak.cpp:41:7:
   FOR(i,g[node].size()){
       ~~~~~~~~~~~~~~~~         
shymbulak.cpp:41:3: note: in expansion of macro 'FOR'
   FOR(i,g[node].size()){
   ^~~
shymbulak.cpp: In function 'std::pair<int, int> maxDpthDFS(int, int)':
shymbulak.cpp:11:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i,n) for(int i=0;i<n;i++)
shymbulak.cpp:76:7:
   FOR(i,g[node].size()){
       ~~~~~~~~~~~~~~~~         
shymbulak.cpp:76:3: note: in expansion of macro 'FOR'
   FOR(i,g[node].size()){
   ^~~
shymbulak.cpp: In function 'int main()':
shymbulak.cpp:163:9: warning: unused variable 'st' [-Wunused-variable]
     int st = IND__ + i;
         ^~

• Subtask 1: 0 / 30
• Subtask 2: 0 / 20
• Subtask 3: 0 / 50