AtCoder Grand Contest 005

Submission #1589718

Source codeソースコード

#include<iostream>
#include<cstdio>
#include<cstring>
#define repst(p) for(int i=begin[p],q;i;i=next[i])if((q=to[i])!=h)
#define rept(p,t) for(int i=t.begin[p],q;i;i=t.next[i])if((q=t.to[i])!=h)
template<typename T>inline void check_max(T a,T &b){if(a>b)b=a;}
template<typename T>inline void read(T &x)
{
	char c=x=0;
	for(c=getchar();!isdigit(c);c=getchar());
	for(;isdigit(c);c=getchar())x=(x<<3)+(x<<1)+(c^48);
}
namespace wrong
{
	const int N=201000,M=N*2;
	struct tool
	{
		int begin[N],next[M],to[M];
		int fa[N][20],dep[N];
		int e;
		void add(int x,int y,bool k=1)
		{
			to[++e]=y;
			next[e]=begin[x];
			begin[x]=e;
			if(k)add(y,x,0);
		}
		void predfs(int p=1,int h=0)
		{
			dep[p]=dep[h]+1;
			for(int k=1;k<=18;k++)
				fa[p][k]=fa[fa[p][k-1]][k-1];
			repst(p)
			{
				fa[q][0]=p;
				predfs(q,p);
			}
		}
		int get_lca(int u,int v)
		{
			if(dep[u]<dep[v])std::swap(u,v);
			for(int k=18;k>=0;k--)
				while(dep[fa[u][k]]>=dep[v])u=fa[u][k];
			for(int k=18;k>=0;k--)
				while(fa[u][k]!=fa[v][k])
					u=fa[u][k],v=fa[v][k];
			return u==v?u:fa[u][0];
		}
		int dis(int u,int v){return dep[u]+dep[v]-2*dep[get_lca(u,v)];}
		bool check(int u,int v)
		{
			if(dep[u]<dep[v])std::swap(u,v);
			if(fa[u][0]==v || fa[u][1]==v)return 0;
			if(fa[u][0]==fa[v][0])return 0;
			return 1;
		}
		int go(int p,int q)
		{
			if(dep[p]>=dep[q])return fa[p][0];
			for(int k=18;k>=0;k--)
				while(dep[fa[q][k]]>dep[p])q=fa[q][k];
			if(fa[q][0]==p)return q;
			return fa[p][0];
		}
	}s,t;
	int f[N],g[N];
	bool isit[N];
	int n,X,Y;
	void initialize()
	{
		read(n),read(X),read(Y);
		for(int i=1,u,v;i<n;i++)
			read(u),read(v),s.add(u,v);
		for(int i=1,u,v;i<n;i++)
			read(u),read(v),t.add(u,v);
		t.predfs();
		f[X]=Y,g[X]=0;
	}
	void dfs(int p=X,int h=0)
	{

		if(p==f[p])return;
		rept(p,s)
		{
			if(t.check(p,q))isit[p]=isit[q]=1;
			if(q==f[p])continue;
			f[q]=t.go(f[p],q);
			g[q]=g[p]+1;
			dfs(q,p);
		}
	}
	int getans()
	{
		int ret=0;
		for(int i=1;i<=n;i++)
		{
			if(!f[i])continue;
			if(f[i]!=i && isit[i])return -1;
//			printf("%d %d %d\n",i,f[i],g[i]);

			check_max(g[i]+t.dis(i,f[i]),ret);
		}
		return ret*2;
	}
	void solve()
	{
		initialize();
		dfs();
		printf("%d\n",getans());
	}
}
int main()
{
//	freopen("in","r",stdin);
	wrong::solve();
	return 0;
}

Submission

Task問題 E - Sugigma: The Showdown
User nameユーザ名 Demerzel_IV
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 1400
Source lengthソースコード長 2405 Byte
File nameファイル名
Exec time実行時間 140 ms
Memory usageメモリ使用量 36736 KB

Test case

Set

Set name Score得点 / Max score Cases
Sample - example0,example1,example2,example3,example4
All 1400 / 1400 doublestar0,doublestar1,doublestar2,doublestar3,doublestar4,doublestar5,doublestar6,doublestar7,example0,example1,example2,example3,example4,giri0,giri1,giri2,giri3,giri4,giri5,giri6,giri7,giri8,giri9,maxrand0,maxrand1,maxrand2,maxrand3,maxrand4,maxrand5,maxrand6,maxrand7,maxrand8,maxrand9,narashi0,narashi1,narashi2,narashi3,narashi4,narashi5,narashi6,narashi7,narashi8,narashi9,ok0,ok1,ok2,ok3,ok4,ok5,ok6,ok7,ok8,ok9,ouh0,ouh1,ouh2,ouh3,ouh4,ouh5,ouh6,ouh7,ouh8,ouh9,same0,same1,same2,same3,same4,same5,same6,same7,same8,same9,sameline0,sameline1,sameline2,sameline3,sameline4,sameline5,sameline6,sameline7,sameline8,sameline9,star0,star1,star2,star3,star4,star5,star6,star7,star8,star9,supersmall0,supersmall1,supersmall2,supersmall3,supersmall4,supersmall5,supersmall6,supersmall7,supersmall8,supersmall9

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
doublestar0 AC 69 ms 26752 KB
doublestar1 AC 66 ms 26752 KB
doublestar2 AC 69 ms 26752 KB
doublestar3 AC 69 ms 26752 KB
doublestar4 AC 74 ms 26880 KB
doublestar5 AC 70 ms 26880 KB
doublestar6 AC 63 ms 26752 KB
doublestar7 AC 64 ms 26752 KB
example0 AC 3 ms 8448 KB
example1 AC 2 ms 8448 KB
example2 AC 2 ms 8448 KB
example3 AC 2 ms 8448 KB
example4 AC 2 ms 8448 KB
giri0 AC 77 ms 26752 KB
giri1 AC 92 ms 26624 KB
giri2 AC 77 ms 26624 KB
giri3 AC 94 ms 26624 KB
giri4 AC 101 ms 26624 KB
giri5 AC 99 ms 26752 KB
giri6 AC 99 ms 26752 KB
giri7 AC 93 ms 26624 KB
giri8 AC 88 ms 26752 KB
giri9 AC 78 ms 26752 KB
maxrand0 AC 87 ms 26880 KB
maxrand1 AC 86 ms 26880 KB
maxrand2 AC 90 ms 26880 KB
maxrand3 AC 85 ms 26880 KB
maxrand4 AC 83 ms 26752 KB
maxrand5 AC 87 ms 26752 KB
maxrand6 AC 84 ms 26752 KB
maxrand7 AC 86 ms 26880 KB
maxrand8 AC 83 ms 26752 KB
maxrand9 AC 90 ms 26880 KB
narashi0 AC 89 ms 26624 KB
narashi1 AC 92 ms 26624 KB
narashi2 AC 89 ms 26624 KB
narashi3 AC 89 ms 26624 KB
narashi4 AC 93 ms 26752 KB
narashi5 AC 89 ms 26624 KB
narashi6 AC 92 ms 26624 KB
narashi7 AC 90 ms 26752 KB
narashi8 AC 99 ms 26752 KB
narashi9 AC 91 ms 26624 KB
ok0 AC 96 ms 34048 KB
ok1 AC 100 ms 33280 KB
ok2 AC 115 ms 30208 KB
ok3 AC 87 ms 32896 KB
ok4 AC 89 ms 32512 KB
ok5 AC 117 ms 32512 KB
ok6 AC 89 ms 35712 KB
ok7 AC 87 ms 32512 KB
ok8 AC 122 ms 31232 KB
ok9 AC 95 ms 33536 KB
ouh0 AC 84 ms 26880 KB
ouh1 AC 76 ms 28416 KB
ouh2 AC 88 ms 28160 KB
ouh3 AC 91 ms 30080 KB
ouh4 AC 100 ms 27776 KB
ouh5 AC 108 ms 34176 KB
ouh6 AC 113 ms 30720 KB
ouh7 AC 85 ms 28928 KB
ouh8 AC 103 ms 29824 KB
ouh9 AC 98 ms 35072 KB
same0 AC 88 ms 26624 KB
same1 AC 90 ms 26624 KB
same2 AC 64 ms 26624 KB
same3 AC 64 ms 26624 KB
same4 AC 66 ms 26624 KB
same5 AC 91 ms 26624 KB
same6 AC 67 ms 26624 KB
same7 AC 94 ms 26624 KB
same8 AC 61 ms 26624 KB
same9 AC 104 ms 26624 KB
sameline0 AC 135 ms 31616 KB
sameline1 AC 140 ms 35968 KB
sameline2 AC 90 ms 31232 KB
sameline3 AC 124 ms 31488 KB
sameline4 AC 82 ms 30080 KB
sameline5 AC 138 ms 34688 KB
sameline6 AC 97 ms 29568 KB
sameline7 AC 129 ms 36736 KB
sameline8 AC 94 ms 31360 KB
sameline9 AC 110 ms 31744 KB
star0 AC 76 ms 26624 KB
star1 AC 72 ms 26624 KB
star2 AC 55 ms 25088 KB
star3 AC 76 ms 26624 KB
star4 AC 78 ms 26624 KB
star5 AC 75 ms 26624 KB
star6 AC 56 ms 25088 KB
star7 AC 79 ms 26624 KB
star8 AC 79 ms 26624 KB
star9 AC 74 ms 26624 KB
supersmall0 AC 3 ms 8448 KB
supersmall1 AC 3 ms 8448 KB
supersmall2 AC 2 ms 8448 KB
supersmall3 AC 2 ms 8448 KB
supersmall4 AC 2 ms 8448 KB
supersmall5 AC 3 ms 8448 KB
supersmall6 AC 2 ms 8448 KB
supersmall7 AC 2 ms 8448 KB
supersmall8 AC 2 ms 8448 KB
supersmall9 AC 3 ms 8448 KB