#83966 (C++11) No.363 門松サイクル

提出ソース

結果

問題	No.363 門松サイクル
ユーザー	koyumeishi
提出日時	2016-03-30 17:41:48
言語	C++11 (gcc 11.4.0)
結果	AC
実行時間	354 ms / 4,000 ms
コード長	8,563 bytes
コンパイル時間	1,203 ms
コンパイル使用メモリ	110,992 KB
実行使用メモリ	42,692 KB
最終ジャッジ日時	2024-10-02 08:15:33
合計ジャッジ時間	6,700 ms
ジャッジサーバーID （参考情報）	judge1 / judge5

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	2 ms 6,816 KB
testcase_02	AC	3 ms 6,816 KB
testcase_03	AC	3 ms 6,820 KB
testcase_04	AC	3 ms 6,816 KB
testcase_05	AC	3 ms 6,816 KB
testcase_06	AC	3 ms 6,816 KB
testcase_07	AC	3 ms 6,816 KB
testcase_08	AC	3 ms 6,816 KB
testcase_09	AC	91 ms 19,200 KB
testcase_10	AC	101 ms 20,908 KB
testcase_11	AC	220 ms 37,268 KB
testcase_12	AC	241 ms 36,148 KB
testcase_13	AC	214 ms 34,716 KB
testcase_14	AC	178 ms 32,216 KB
testcase_15	AC	192 ms 35,080 KB
testcase_16	AC	151 ms 24,832 KB
testcase_17	AC	346 ms 39,424 KB
testcase_18	AC	282 ms 37,508 KB
testcase_19	AC	219 ms 41,140 KB
testcase_20	AC	284 ms 37,444 KB
testcase_21	AC	354 ms 39,488 KB
testcase_22	AC	245 ms 36,560 KB
testcase_23	AC	249 ms 32,512 KB
testcase_24	AC	2 ms 6,816 KB
testcase_25	AC	2 ms 6,820 KB
testcase_26	AC	183 ms 42,692 KB
testcase_27	AC	177 ms 41,572 KB
testcase_28	AC	244 ms 41,576 KB

権限があれば一括ダウンロードができます

コンパイルメッセージ

main.cpp: In function ‘exstd::FastInStream& exstd::operator>>(exstd::FastInStream&, int&)’:
main.cpp:28:76: warning: ignoring return value of ‘int fscanf(FILE*, const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   28 |         inline FastInStream& operator >> (FastInStream& is, int& v){ fscanf(is.filePointer, "%d", &v); return is;}
      |                                                                      ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

ソースコード

raw source code

#include <iostream>
#include <vector>
#include <cstdio>
#include <sstream>
#include <map>
#include <string>
#include <algorithm>
#include <queue>
#include <cmath>
#include <functional>
#include <set>
#include <ctime>
#include <random>
#include <chrono>
#include <cassert>
using namespace std;

namespace exstd{
	char buff[200000];
	class FastInStream{
	public:
		FILE* filePointer;
		FastInStream(){filePointer = stdin;}
		FastInStream(FILE* fp){filePointer = fp;}
		template<class H> inline void get(H& h);
		template<class H, class ... T> inline void get(H& h, T& ... t);
	};
	inline FastInStream& operator >> (FastInStream& is, int& v){ fscanf(is.filePointer, "%d", &v); return is;}
	inline FastInStream& operator >> (FastInStream& is, long long& v){ fscanf(is.filePointer, "%lld", &v); return is;}
	inline FastInStream& operator >> (FastInStream& is, double& v){ fscanf(is.filePointer, "%lf", &v); return is;}
	inline FastInStream& operator >> (FastInStream& is, string& v){ fscanf(is.filePointer, "%s", buff); v = buff; return is;}
	//inline FastInStream& operator >> (FastInStream& is, __int128& v){v = 0;string s; is >> s;int sgn = 1;int p = 0;if(s[p] == '-'){ sgn=-1; p++;}for(;p<s.size(); p++){ v *= 10; v += s[p]-'0'; }v *= sgn;return is;}
	template<class T> FastInStream& operator >> (FastInStream& is, vector<T>& vec){ for(auto& v: vec) is >> v; return is;}
	template<class T> FastInStream& operator ,  (FastInStream& is, T& v){ return is >> v; }
	template<class H> inline void FastInStream::get(H& h){(*this) >> h;}
	template<class H, class ... T> inline void FastInStream::get(H& h, T& ... t){
		(*this) >> h; FastInStream::get(t...);
	}

	struct FastOutEndLine{ int dammy; } fendl;
	struct FastOutEndLineFlush{ int dammy; } fendlf;

	class FastOutStream{
	public:
		FILE* filePointer;
		FastOutStream(){filePointer = stdout;}
		FastOutStream(FILE* fp){filePointer = fp;}
		template<class H> inline void print(const H& h);
		template<class H, class ... T> void print(const H& h, const T& ... t);
		template<class H> inline void println(const H& h);
		template<class H, class ... T> void println(const H& h, const T& ... t);
		void flush(){fflush(filePointer);}
	};
	inline FastOutStream& operator << (FastOutStream& os, const FastOutEndLine& v){ fprintf(os.filePointer, "\n"); return os; }
	inline FastOutStream& operator << (FastOutStream& os, const FastOutEndLineFlush& v){ fprintf(os.filePointer, "\n"); fflush(os.filePointer); return os; }
	inline FastOutStream& operator << (FastOutStream& os, const int& v){ fprintf(os.filePointer, "%d", v); return os; }
	inline FastOutStream& operator << (FastOutStream& os, const long long& v){ fprintf(os.filePointer, "%lld", v); return os; }
	inline FastOutStream& operator << (FastOutStream& os, const double& v){ fprintf(os.filePointer, "%.12f", v); return os; }
	inline FastOutStream& operator << (FastOutStream& os, const string& v){ fprintf(os.filePointer, "%s", v.c_str()); return os; }
	//FastOutStream& operator << (FastOutStream& os, __int128 v){if(v==0) return os << 0;int sgn = 1;if(v<0){ sgn = -1; v = -v; }string tmp;while(v>0){ tmp.push_back('0' + v%10); v/=10; }if(sgn<0) tmp.push_back('-');reverse(tmp.begin(), tmp.end());return os << tmp;}
	template<class T> FastOutStream& operator << (FastOutStream& os, const vector<T>& vec){ for(int i=0; i<vec.size(); i++) os << (i?" ":"") << vec[i]; return os; }
	template<class T> inline FastOutStream& operator ,  (FastOutStream& os, const T& v){ return os << v; }
	template<class H> inline void FastOutStream::print(const H& h){ (*this) << h; }
	template<class H, class ... T> void FastOutStream::print(const H& h, const T& ... t){
		(*this) << h << " "; FastOutStream::print(t...);
	}
	template<class H> inline void FastOutStream::println(const H& h){ (*this) << h << "\n"; }
	template<class H, class ... T> void FastOutStream::println(const H& h, const T& ... t){
		(*this) << h << " "; FastOutStream::println(t...);
	}

	FastInStream fin;
	FastOutStream fout;
	FastOutStream ferr(stderr);
}
using namespace exstd;

class HeavyLightDecomposition{
public:
	struct heavy_set{
		vector<int> element;
		int depth;
		int parent_vertex;
		heavy_set(int v, int d, int par) : element(1,v), depth(d), parent_vertex(par){}
	};

	vector<vector<int>>& G;
	vector<heavy_set> S;
	vector<int> subtree_size;
	vector<int> set_index;
	vector<int> ele_index;

private:
	int get_subtree_size(int pos, int par){
		int sz = 1;
		for(int ch : G[pos]){
			if(ch == par) continue;
			sz += get_subtree_size(ch, pos);
		}
		return subtree_size[pos] = sz;
	}

	void make_path(int pos, int par, int set_id){
		set_index[pos] = set_id;
		ele_index[pos] = S[set_id].element.size()-1;

		int largest_child = -1;
		int value = 0;

		for(int ch : G[pos]){
			if(ch == par) continue;
			if(value < subtree_size[ch]){
				value = subtree_size[ch];
				largest_child = ch;
			}
		}

		for(int ch : G[pos]){
			if(ch == par) continue;
			if(largest_child == ch){
				S[set_id].element.push_back(ch);
				make_path(ch, pos, set_id);
			}else{
				S.emplace_back( ch, S[set_id].depth+1, pos );
				make_path(ch, pos, S.size()-1);
			}
		}
	}

	void init(int root){
		subtree_size.resize(G.size(), 0);
		get_subtree_size(root,root);

		set_index.resize(G.size(), 0);
		ele_index.resize(G.size(), 0);

		S.emplace_back( root,0,root );

		make_path( root, root, 0 );

		subtree_size.clear();
	}

public:
	HeavyLightDecomposition(vector<vector<int>>& G_, int root = 0) : G(G_){
		init(root);
	}

	//set_index, element_index
	//S[set_index].element[element_index] == v
	pair<int,int> get_position(int v){
		return {set_index[v], ele_index[v]};
	}
};

int LCA(HeavyLightDecomposition& T, int u, int v){
	auto pu = T.get_position(u);
	auto pv = T.get_position(v);
	if(pu.first == pv.first){
		return pu.second < pv.second ? u : v;
	}

	if(T.S[pu.first].depth > T.S[pv.first].depth){
		swap(pu, pv);
		swap(u,v);
	}

	while(T.S[pu.first].depth != T.S[pv.first].depth){
		v = T.S[pv.first].parent_vertex;
		pv = T.get_position( v );
	}

	while(pu.first != pv.first){
		u = T.S[pu.first].parent_vertex;
		v = T.S[pv.first].parent_vertex;
		pu = T.get_position(u);
		pv = T.get_position(v);
		if(T.S[pv.first].depth == 0) break;
		if(T.S[pv.first].depth == 0) break;
	}

	if(pu.first == pv.first){
		return pu.second < pv.second ? u : v;
	}else{
		abort();
	}
	return -1;
}

inline bool is_kadomatsu(int a, int b, int c){
	return a!=c && ((a<b&&b>c) || (a>b&&b<c));
}

int main(){
	int n;
	fin >> n;
	vector<int> a(n);
	fin >> a;

	vector<vector<int>> G(n);
	for(int i=0; i<n-1; i++){
		int u,v;
		fin >> u,v;
		u--; v--;
		G[u].push_back(v);
		G[v].push_back(u);
	}


	vector<vector<int>> par(n, vector<int>(20));
	vector<vector<int>> kad(n, vector<int>(20));
	vector<int> dep(n, -1);

	function<void(int,int)> dfs = [&](int pos, int last){
		dep[pos] = dep[last]+1;
		par[pos][0] = last;
		if(is_kadomatsu(a[pos], a[last], a[par[last][0]])){
			kad[pos][0] = 1;
		}else{
			kad[pos][0] = 0;
		}
		for(int next : G[pos]){
			if(next == last) continue;
			dfs(next, pos);
		}
	};

	mt19937 mt(chrono::duration_cast<chrono::nanoseconds>(chrono::steady_clock::now().time_since_epoch()).count());
	int root = uniform_int_distribution<int>(0, n-1)(mt);
	dfs(root,root);

	HeavyLightDecomposition T(G, root);

	for(int k=1; k<20; k++){
		for(int i=0; i<n; i++){
			kad[i][k] = kad[i][k-1] & kad[par[i][k-1]][k-1];
			par[i][k] = par[par[i][k-1]][k-1];
		}
	}

	auto k_anc = [&](int pos, int k){
		int b=0;
		while(k){
			if(k&1) pos = par[pos][b];
			b++;
			k >>= 1;
		}
		return pos;
	};

	auto kadomatsu_line = [&](int u, int p) -> bool{
		int d = dep[u] - dep[p] - 2;
		if(d<0) return true;

		d++;

		int ret = kad[u][0];
		int b = 0;
		while(d>0){
			if(d&1){
				ret &= kad[u][b];
				u = par[u][b];
			}
			b++;
			d>>=1;
		}
		return ret;
	};

	int q;
	fin >> q;

	while(q--){
		int u,v;
		fin >> u,v;

		u--; v--;

		if(dep[u] < dep[v]) swap(u,v);
		int p = LCA(T, u,v);
		if(p==v){
			int pu = k_anc(u, dep[u]-dep[p]-1);
			int qu = par[u][0];
			bool ok = (
				is_kadomatsu(a[pu],a[p],a[u]) && 
				is_kadomatsu(a[p],a[u],a[qu]) &&
				kadomatsu_line(u, p)
				);
			fout << (ok?"YES":"NO") << fendl;

		}else{
			int pu = k_anc(u, dep[u]-dep[p]-1);
			int pv = k_anc(v, dep[v]-dep[p]-1);
			int qu = par[u][0];
			int qv = par[v][0];

			bool ok = (
				is_kadomatsu(a[pu], a[p], a[pv]) &&
				is_kadomatsu(a[qu], a[u], a[v]) &&
				is_kadomatsu(a[u], a[v], a[qv]) &&
				kadomatsu_line(u,p) &&
				kadomatsu_line(v,p)
				);

			fout << (ok?"YES":"NO") << fendl;
		}
	}

	return 0;
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード