Submission #534414


Source Code Expand

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#include <functional>
#include <map>
#include <set>
#include <cmath>
#define SIZE 100005
#define BT 20

using namespace std;
typedef long long int ll;
typedef pair <int,int> P;

vector <int> vec[SIZE];
vector <int> Q[SIZE];
vector <int> memo[SIZE];
bool use[SIZE];
int A[SIZE],nd[SIZE];
int col[SIZE];
int X[SIZE],V[SIZE],W[SIZE];
int n,q;

int Count(int v,int p)
{
	Q[v].clear();
	nd[v]=1;
	for(int i=0;i<vec[v].size();i++)
	{
		int to=vec[v][i];
		if(to!=p&&!use[to])
		{
			nd[v]+=Count(to,v);
		}
	}
	return nd[v];
}
void Coloring(int v,int p,int c)
{
	col[v]=c;
	for(int i=0;i<vec[v].size();i++)
	{
		int to=vec[v][i];
		if(to!=p&&!use[to])
		{
			Coloring(to,v,c);
		}
	}
}
P center(int v,int p,int all)
{
	P ret=P(all,v);
	int mx=all-nd[v];
	for(int i=0;i<vec[v].size();i++)
	{
		int to=vec[v][i];
		if(to!=p&&!use[to])
		{
			ret=min(ret,center(to,v,all));
			mx=max(mx,nd[to]);
		}
	}
	ret=min(ret,P(mx,v));
	return ret;
}
set <P> solve1(int v,int p)
{
	set <P> st;
	set <P>::iterator it,its;
	for(int i=0;i<Q[v].size();i++)
	{
		int id=Q[v][i];
		st.insert(P(X[id],id));
	}
	for(int i=0;i<vec[v].size();i++)
	{
		int to=vec[v][i];
		if(to!=p&&!use[to])
		{
			set <P> nxt=solve1(to,v);
			if(nxt.size()>st.size()) swap(nxt,st);//nxt.size()<=st.size()
			for(it=nxt.begin();it!=nxt.end();it++) st.insert(*it);
		}
	}
	it=st.lower_bound(P(A[v],-1));
	while(it!=st.end())
	{
		int to=it->second;
		X[to]%=A[v];
		its=it;its++;
		st.erase(it);
		st.insert(P(X[to],to));
		it=its;
	}
	return st;
}
void solve(int v,vector <int> query)
{
	int all=Count(v,-1);
	int ct=center(v,-1,all).second;
	use[ct]=true;
	col[ct]=-1;
	for(int i=0;i<vec[ct].size();i++)
	{
		int to=vec[ct][i];
		if(!use[to])
		{
			memo[to].clear();
			Coloring(to,ct,to);
		}
	}
	for(int i=0;i<query.size();i++)
	{
		int id=query[i];
		if(col[V[id]]!=col[W[id]]||V[id]==ct)
		{
			Q[V[id]].push_back(id);
			V[id]=col[W[id]];
		}
	}
	solve1(ct,-1);
	for(int i=0;i<query.size();i++)
	{
		int id=query[i];
		if(V[id]!=-1)
		{
			memo[col[V[id]]].push_back(id);
		}
	}
	for(int i=0;i<vec[ct].size();i++)
	{
		int to=vec[ct][i];
		if(!use[to])
		{
			solve(to,memo[to]);
		}
	}
}
int main()
{
	scanf("%d %d",&n,&q);
	for(int i=0;i<n;i++) scanf("%d",&A[i]);
	for(int i=0;i<n-1;i++)
	{
		int a,b;
		scanf("%d %d",&a,&b);a--;b--;
		vec[a].push_back(b);
		vec[b].push_back(a);
	}
	vector <int> query;
	for(int i=0;i<q;i++)
	{
		scanf("%d %d %d",&X[i],&V[i],&W[i]);
		V[i]--;W[i]--;
		query.push_back(i);
	}
	solve(0,query);
	for(int i=0;i<q;i++) printf("%d\n",X[i]);
	return 0;
}

Submission Info

Submission Time
Task J - MODクエリ
User yutaka1999
Language C++ (GCC 4.9.2)
Score 400
Code Size 2822 Byte
Status AC
Exec Time 1080 ms
Memory 38628 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:144:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&q);
                      ^
./Main.cpp:145:40: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0;i<n;i++) scanf("%d",&A[i]);
                                        ^
./Main.cpp:149:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&a,&b);a--;b--;
                       ^
./Main.cpp:156:38: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d",&X[i],&V[i],&W[i]);
                                      ^

Judge Result

Set Name Small All
Score / Max Score 30 / 30 370 / 370
Status
AC × 16
AC × 38
Set Name Test Cases
Small 00_sample_path_01.txt, 15_path_00.txt, 15_path_01.txt, 15_path_02.txt, 15_path_03.txt, 15_path_04.txt, 16_path_05.txt, 16_path_06.txt, 16_path_07.txt, 16_path_08.txt, 16_path_09.txt, 17_path_10.txt, 17_path_11.txt, 17_path_12.txt, 17_path_13.txt, 17_path_14.txt
All 00_sample_path_01.txt, 15_path_00.txt, 15_path_01.txt, 15_path_02.txt, 15_path_03.txt, 15_path_04.txt, 16_path_05.txt, 16_path_06.txt, 16_path_07.txt, 16_path_08.txt, 16_path_09.txt, 17_path_10.txt, 17_path_11.txt, 17_path_12.txt, 17_path_13.txt, 17_path_14.txt, 20_random_15.txt, 20_random_16.txt, 20_random_17.txt, 21_random_18.txt, 21_random_19.txt, 21_random_20.txt, 30_random_21.txt, 30_random_22.txt, 30_random_23.txt, 40_random_24.txt, 40_random_25.txt, 40_random_26.txt, 49_sample_02.txt, 61_test_27.txt, 61_test_28.txt, 61_test_29.txt, 63_star_30.txt, 63_star_31.txt, 63_star_32.txt, 64_three_33.txt, 64_three_34.txt, 64_three_35.txt
Case Name Status Exec Time Memory
00_sample_path_01.txt AC 40 ms 7956 KB
15_path_00.txt AC 40 ms 7836 KB
15_path_01.txt AC 39 ms 7836 KB
15_path_02.txt AC 39 ms 7964 KB
15_path_03.txt AC 38 ms 7836 KB
15_path_04.txt AC 39 ms 7848 KB
16_path_05.txt AC 38 ms 7840 KB
16_path_06.txt AC 40 ms 7848 KB
16_path_07.txt AC 39 ms 7848 KB
16_path_08.txt AC 37 ms 7844 KB
16_path_09.txt AC 39 ms 7840 KB
17_path_10.txt AC 891 ms 38624 KB
17_path_11.txt AC 801 ms 38628 KB
17_path_12.txt AC 812 ms 38556 KB
17_path_13.txt AC 805 ms 38576 KB
17_path_14.txt AC 793 ms 38604 KB
20_random_15.txt AC 40 ms 7836 KB
20_random_16.txt AC 41 ms 7844 KB
20_random_17.txt AC 43 ms 7852 KB
21_random_18.txt AC 40 ms 7848 KB
21_random_19.txt AC 40 ms 7844 KB
21_random_20.txt AC 42 ms 7836 KB
30_random_21.txt AC 40 ms 7840 KB
30_random_22.txt AC 39 ms 7844 KB
30_random_23.txt AC 40 ms 7840 KB
40_random_24.txt AC 859 ms 23628 KB
40_random_25.txt AC 856 ms 23748 KB
40_random_26.txt AC 883 ms 23732 KB
49_sample_02.txt AC 40 ms 7844 KB
61_test_27.txt AC 1079 ms 32032 KB
61_test_28.txt AC 1074 ms 32120 KB
61_test_29.txt AC 1080 ms 30340 KB
63_star_30.txt AC 421 ms 21084 KB
63_star_31.txt AC 411 ms 21080 KB
63_star_32.txt AC 423 ms 21148 KB
64_three_33.txt AC 998 ms 32992 KB
64_three_34.txt AC 1024 ms 33544 KB
64_three_35.txt AC 993 ms 31832 KB