[USACO 2010 Hol G]Cow Politics

C++14(g++5.4) 解法, 执行用时: 203ms, 内存消耗: 53088K, 提交时间: 2020-01-11 17:16:38

#pragma GCC target("popcnt")
#pragma GCC optimize("Ofast,inline")
#pragma comment(linker,"/STACK:1024000000,1024000000")
#undef __STRICT_ANSI__
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <string>
#include <cstring>
#include <cctype>
#include <sstream>
#include <cfloat>
#include <complex>
#include <climits>
#include <new>
#include <memory>
#include <cerrno>
#include <cassert>
#include <ctime>
#include <set>
#include <map>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <vector>
#include <bitset>
#include <utility>
#include <iterator>
#include <iostream>
#include <fstream>
#include <iomanip>
#include <numeric>
#include <cstddef>
#include <algorithm>
#include <functional>
#include <unordered_map>
#include <unordered_set>
#include <streambuf>
#include <cfenv>
#include <tuple>
#include <cstdint>
#include <random>
#include <regex>
#define lc c[0]
#define rc c[1]
#define fir first
#define sec second
#define lson x<<1
#define rson x<<1|1
#define PB push_back
#define PF push_front
#define MP make_pair
#define MT make_tuple
#define EB emplace_back
#define EF emplace_front
#define Lson l,m,lson
#define Rson m+1,r,rson
#define LB lower_bound
#define UB upper_bound
#define npos string::npos
#define FF fflush(stdout)
#define PQ priority_queue
#define rint register int
#define LSON L,m,l,m,lson
#define RSON m+1,R,m+1,r,rson
#define sqr(X) ((X)*(X))
#define cbr(X) ((X)*(X)*(X))
#define LBT(X) ((X)&(-(X)))
#define SZ(X) (int)(X).size()
#define ALL(X) (X).begin(),(X).end()
#define INS(X) inserter((X),(X).begin())
#define POS(X,Y,Z) LB((X),(Y),(Z))-(X)+1
#define CPY(X,Y) memcpy((X),(Y),sizeof((Y)))
#define MEM(X,Y) memset((X),(Y),sizeof((X)))
#define SC(X) while(scanf("%s",(X)),!strlen((X)))
#define NUM(X,Y,L,R) UB((X),(Y),(R))-LB((X),(Y),(L))
#define SU(X,Y,Z) sort((X),(Y)),(Z)=unique((X),(Y))-(X)
#define FIO ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define INF 0x3f3f3f3f
#define NNF 0xc0c0c0c0
#define INF64 0x3f3f3f3f3f3f3f3fLL
#define NNF64 0xc0c0c0c0c0c0c0c0LL
#define PH 0.75
#define P 131
using namespace std;
typedef long long LL;
typedef long double LD;
typedef unsigned int UI;
typedef unsigned long long ULL;
typedef pair<LL,LL> PLL;
typedef pair<int,LL> PIL;
typedef pair<LL,int> PLI;
typedef pair<int,int> PII;
typedef pair<char,int> PCI;
typedef pair<int,char> PIC;
typedef pair<int,string> PIS;
typedef pair<string,int> PSI;
typedef pair<double,int> PDI;
typedef pair<int,double> PID;
typedef pair<double,double> PDD;
typedef pair<string,string> PSS;
typedef tuple<LL,LL,LL> PLLL;
typedef tuple<LL,LL,int> PLLI;
typedef tuple<int,LL,LL> PILL;
typedef tuple<LL,int,int> PLII;
typedef tuple<int,int,LL> PIIL;
typedef tuple<int,int,int> PIII;
typedef tuple<LL,LL,LL,LL> PLLLL;
typedef tuple<int,int,int,int> PIIII;
typedef tuple<double,double,int> PDDI;
typedef tuple<double,double,double> PDDD;
typedef tuple<double,double,double,int> PDDDI;
typedef set<LL> SL;
typedef set<int> SI;
typedef set<PII> SPII;
typedef set<PIL> SPIL;
typedef set<PLI> SPLI;
typedef set<PLL> SPLL;
typedef set<PIII> SPIII;
typedef set<PLLL> SPLLL;
typedef set<string> SS;
typedef queue<LL> QL;
typedef queue<int> QI;
typedef queue<PII> QPII;
typedef queue<PIL> QPIL;
typedef queue<PLI> QPLI;
typedef queue<PLL> QPLL;
typedef deque<LL> DL;
typedef deque<int> DI;
typedef deque<PII> DPII;
typedef deque<PIL> DPIL;
typedef deque<PLI> DPLI;
typedef deque<PLL> DPLL;
typedef complex<LL> CL;
typedef complex<int> CI;
typedef complex<double> CD;
typedef vector<LL> VL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef vector<PII> VPII;
typedef vector<PIL> VPIL;
typedef vector<PLI> VPLI;
typedef vector<PLL> VPLL;
typedef vector<PIC> VPIC;
typedef vector<PCI> VPCI;
typedef vector<PID> VPID;
typedef vector<PDI> VPDI;
typedef vector<PIS> VPIS;
typedef vector<PSI> VPSI;
typedef vector<string> VS;
typedef vector<PIII> VPIII;
typedef vector<PIIL> VPIIL;
typedef vector<PILL> VPILL;
typedef vector<PLLL> VPLLL;
typedef vector<PLII> VPLII;
typedef vector<PLLI> VPLLI;
typedef vector<PIIII> VPIIII;
typedef vector<PLLLL> VPLLLL;
typedef map<LL,LL> MLL;
typedef map<int,LL> MIL;
typedef map<LL,int> MLI;
typedef map<int,int> MII;
typedef map<PII,int> MPIII;
typedef map<PLL,int> MPLLI;
typedef map<string,int> MSI;
typedef map<VI,int> MVII;
template<typename T> T gcd(T x,T y) {return y?gcd(y,x%y):x;}
template<typename T> T lcm(T x,T y) {return x/gcd(x,y)*y;}
template<typename T> void adn(T &x,T y,T z) {x=min(z,x+y);}
template<typename T> void adm(T &x,T y,T z) {x=x+y;if(x>=z)x=x-z;}
template<typename T> void adj(T &x,T y) {if(x>=y||x<=-y)x=x%y;if(x<0)x=x+y;}
template<typename T> T qpow(T x,LL y,T z) {for(;y;y>>=1,x=x*x)if(y&1)z=z*x;return z;}
template<typename T> T mpow(LL w,T x,LL y,T z) {for(;y;y>>=1,x=x*x,x=x%w)if(y&1)z=z*x,z=z%w;return z;}
template<typename T> T exgcd(T a,T b,T &x,T &y) {T t=a;b?(t=exgcd(b,a%b,y,x),y=y-(a/b)*x):(x=1,y=0);return t;}
const double EPS = 1e-7;
const LL MOD = 1000000007LL;
const int M = 5000005;
const int N = 200005;
int n,m,dep[N],ed,in[N],dp[19][N<<1],mm[N<<1],t,tt,d[N<<1],mx,mxi,ans,rt;
VI g[N],vec[N];

void dfs(int x,int y)
{
    in[x]=++ed;
    dep[d[ed]=x]=dep[y]+1;
    for (auto &i : g[x])
    if (i^y)
    {
        dfs(i,x);
        d[++ed]=x;
    }
}

void st()
{
    mm[0]=-1;
    for (int i=1;i<=ed;i++)
    {
        dp[0][i]=d[i];
        mm[i]=((i&(i-1)) ? mm[i-1] : mm[i-1]+1);
    }
    for (int i=1;(1<<i)<=ed;i++)
    for (int j=1;j+(1<<i)-1<=ed;j++)
    dp[i][j]=(dep[dp[i-1][j]]<dep[dp[i-1][j+(1<<i-1)]] ? dp[i-1][j] : dp[i-1][j+(1<<i-1)]);
}

int rmq(int x,int y)
{
    int l=min(in[x],in[y]),r=max(in[x],in[y]),t=mm[r-l+1];
    return (dep[dp[t][l]]<dep[dp[t][r-(1<<t)+1]] ? dp[t][l] : dp[t][r-(1<<t)+1]);
}

int main()
{
    scanf("%d %d",&n,&m);
    for (int i=1;i<=n;i++)
    {
        scanf("%d %d",&t,&tt);
        vec[t].PB(i);
        if (tt) g[tt].PB(i); else rt=i;
    }
    dfs(rt,0);
    st();
    for (int i=1;i<=m;i++)
    if (SZ(vec[i]))
    {
        mx=ans=0;
        for (auto &j : vec[i]) 
        if (dep[j]>mx) mx=dep[j],mxi=j;
        for (auto &j : vec[i]) ans=max(ans,dep[mxi]+dep[j]-2*dep[rmq(mxi,j)]);
        printf("%d\n",ans);
    }
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 260ms, 内存消耗: 27996K, 提交时间: 2020-01-11 10:40:50

#include<cstdio>
#include<algorithm>
#include<cctype>
#define maxn 200007
using namespace std;
int n,k,num,rt,head[maxn],f[maxn][22],d[maxn],dis[maxn>>1],a[maxn],b[maxn],c[maxn];
inline int qread() {
  char c=getchar();int num=0,f=1;
  for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
  for(;isdigit(c);c=getchar()) num=num*10+c-'0';
  return num*f;
}
struct Edge {
  int v,nxt;
}e[maxn<<1];
inline void ct(int u, int v) {
  e[++num].v=v;
  e[num].nxt=head[u];
  head[u]=num;
}
void dfs(int u, int fa) {
  for(int i=head[u];i;i=e[i].nxt) {
    int v=e[i].v;
    if(v!=fa) {
      f[v][0]=u;
      d[v]=d[u]+1;
      dfs(v,u);
    }
  }
}
inline int lca(int a,int b) {
  if(d[a]>d[b]) swap(a,b);
  for(int i=20;i>=0;--i)
  if(d[a]<=d[b]-(1<<i)) b=f[b][i];
  if(a==b) return a;
  for(int i=20;i>=0;--i)
  if(f[a][i]!=f[b][i]) a=f[a][i],b=f[b][i];
  return f[a][0];
}
int main() {
  n=qread(),k=qread();
  for(int i=1,u;i<=n;++i) {
    a[i]=qread(),u=qread();
    if(!u) {rt=i;continue;}
    ct(u,i);ct(i,u);
  }
  dfs(rt,0);
  for(int i=1;i<=n;++i) {
    if(d[i]>b[a[i]]) {
      c[a[i]]=i;
      b[a[i]]=d[i];
    }
  }
  for(int j=1;j<=20;++j)
  for(int i=1;i<=n;++i)
  f[i][j]=f[f[i][j-1]][j-1];
  for(int i=1;i<=n;++i) 
  dis[a[i]]=max(b[a[i]]+d[i]-2*d[lca(c[a[i]],i)],dis[a[i]]);
  for(int i=1;i<=k;++i)
  printf("%d\n",dis[i]);
  return 0;
}

详情