Submission #12130076


Source Code Expand

Copy
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"
#include "cassert"
#include "ctime"

using namespace std;

constexpr long long int MOD = 1000000007;
//constexpr int MOD = 1000000007;
//constexpr int MOD = 998244353;
//constexpr long long int MOD = 998244353;
constexpr long double EPS = 1e-8;

long long int N, M, K, L, R, H, W;
//int N, M, K, L, R, H, W;

void Calculate_Depth(vector<vector<int>>&edge, vector<int>&depth, int stnode) {
	depth[stnode] = 0;
	queue<int>Q;
	Q.push(stnode);
	while (!Q.empty()) {
		int cn = Q.front();
		Q.pop();
		for (auto i : edge[cn]) {
			if (depth[i] > depth[cn] + 1) {
				depth[i] = depth[cn] + 1;
				Q.push(i);
			}
		}
	}
	return;
}

class EulerTour {	//	0-indexed
public:
	vector<int>tour;
	vector<int>depth;
	vector<int>l;
	vector<int>r;
private:
	int node;
	vector<vector<int>>edge;
	int root = 0;
	void DFS(int n) {
		tour.push_back(n);
		for (auto i : edge[n]) {
			if (depth[n] < depth[i]) {
				DFS(i);
			}
		}
		tour.push_back(n);
		return;
	}
	void BFS() {
		for (auto &i : depth)i = MOD;
		depth[root] = 0;
		queue<int>Q;
		Q.push(root);
		while (!Q.empty()) {
			int cn = Q.front();
			int c = depth[cn];
			Q.pop();
			for (auto i : edge[cn]) {
				if (depth[i] > c + 1) {
					depth[i] = c + 1;
					Q.push(i);
				}
			}
		}
		return;
	}
public:
	EulerTour(int n, int ro) {
		node = n;
		node++;
		root = ro;
		edge.resize(node);
		depth.resize(node, MOD);
		l.resize(node, MOD);
		r.resize(node, 0);
		return;
	}
	void Add_Edge(int a, int b) {
		edge[a].push_back(b);
		edge[b].push_back(a);
		return;
	}
	void Retour() {
		if (!tour.empty())tour.clear();
		BFS();
		DFS(root);
		for (int i = 0; i < tour.size(); i++) {
			l[tour[i]] = min(l[tour[i]], i);
			r[tour[i]] = max(r[tour[i]], i);
		}
		return;
	}
};

class Add_Segment_Tree {
	vector<long long int>v;
	vector<long long int>add;
	vector<long long int>modi;
	vector<int>l;
	vector<int>r;
	int num;
	long long int ret;
	void Left(int place) {
		if (place >= v.size() / 2) {
			l[place] = place - v.size() / 2;
			return;
		}
		Left(place * 2);
		Left(place * 2 + 1);
		l[place] = l[place * 2];
		return;
	}
	void Right(int place) {
		if (place >= v.size() / 2) {
			r[place] = place - v.size() / 2;
			return;
		}
		Right(place * 2);
		Right(place * 2 + 1);
		r[place] = r[place * 2 + 1];
		return;
	}
	long long int Update(int place) {
		if (place >= v.size() / 2) {
			return v[place];
		}
		v[place] = Update(place * 2) + Update(place * 2 + 1);
		return v[place];
	}
	void Modify(int a, int b, long long int num, int place) {
		if (l[place] >= a && r[place] <= b) {
			modi[place] = num * (r[place] - l[place] + 1);
			v[place] = num * (r[place] - l[place] + 1);
			add[place] = 0;
			return;
		}
		if (l[place] > b || r[place] < a)return;
		if (modi[place] != LLONG_MAX) {
			modi[place * 2] = modi[place * 2 + 1] = modi[place] / 2;
			v[place * 2] = v[place * 2 + 1] = modi[place] / 2;
			add[place * 2] = add[place * 2 + 1] = 0;
			modi[place] = LLONG_MAX;
		}
		add[place * 2] += add[place] / 2;
		add[place * 2 + 1] += add[place] / 2;
		add[place] = 0;
		Modify(a, b, num, place * 2);
		Modify(a, b, num, place * 2 + 1);
		v[place] = v[place * 2] + add[place * 2] + v[place * 2 + 1] + add[place * 2 + 1];
		return;
	}
	void Add(int a, int b, long long int num, int place) {
		if (l[place] >= a && r[place] <= b) {
			if (modi[place] != LLONG_MAX) {
				if (place * 2 < v.size()) {
					modi[place * 2] = modi[place * 2 + 1] = modi[place] / 2;
					v[place * 2] = v[place * 2 + 1] = modi[place] / 2;
					add[place * 2] = add[place * 2 + 1] = 0;
				}
				modi[place] = LLONG_MAX;
			}
			add[place] += num * (r[place] - l[place] + 1);
			return;
		}
		if (l[place] > b || r[place] < a)return;
		if (modi[place] != LLONG_MAX) {
			modi[place * 2] = modi[place * 2 + 1] = modi[place] / 2;
			v[place * 2] = v[place * 2 + 1] = modi[place] / 2;
			add[place * 2] = add[place * 2 + 1] = 0;
			modi[place] = LLONG_MAX;
		}
		add[place * 2] += add[place] / 2;
		add[place * 2 + 1] += add[place] / 2;
		add[place] = 0;
		Add(a, b, num, place * 2);
		Add(a, b, num, place * 2 + 1);
		v[place] = v[place * 2] + add[place * 2] + v[place * 2 + 1] + add[place * 2 + 1];
		return;
	}
	void Sum(int a, int b, int place) {
		if (l[place] >= a && r[place] <= b) {
			if (modi[place] != LLONG_MAX) {
				if (place * 2 < v.size()) {
					modi[place * 2] = modi[place * 2 + 1] = modi[place] / 2;
					v[place * 2] = v[place * 2 + 1] = modi[place] / 2;
					add[place * 2] = add[place * 2 + 1] = 0;
				}
				modi[place] = LLONG_MAX;
			}
			ret += v[place] + add[place];
			return;
		}
		if (l[place]>b || r[place]<a) return;
		if (modi[place] != LLONG_MAX) {
			modi[place * 2] = modi[place * 2 + 1] = modi[place] / 2;
			v[place * 2] = v[place * 2 + 1] = modi[place] / 2;
			add[place * 2] = add[place * 2 + 1] = 0;
			modi[place] = LLONG_MAX;
		}
		add[place * 2] += add[place] / 2;
		add[place * 2 + 1] += add[place] / 2;
		add[place] = 0;
		Sum(a, b, place * 2);
		Sum(a, b, place * 2 + 1);
		v[place] = v[place * 2] + add[place * 2] + v[place * 2 + 1] + add[place * 2 + 1];
		return;
	}
public:
	Add_Segment_Tree(int n) {
		n++;
		num = 1;
		while (num < n * 2) {
			num *= 2;
		}
		l.resize(num);
		r.resize(num);
		v.resize(num, 0);
		add.resize(num, 0);
		modi.resize(num, LLONG_MAX);
		Left(1);
		Right(1);
	}
	void Insert(int place, long long int num, bool update) {
		place += v.size() / 2;
		v[place] = num;
		if (!update)return;
		place /= 2;
		while (place) {
			v[place] = v[place * 2] + v[place * 2 + 1];
			place /= 2;
		}
	}
	void Modify(int a, int b, long long int num) {
		Modify(a, b, num, 1);
	}
	void Add(int a, int b, long long int num) {
		Add(a, b, num, 1);
	}
	void Init() {
		Update(1);
	}
	long long int Sum(int a, int b) {
		ret = 0;
		Sum(a, b, 1);
		return ret;
	}
};

void Search(vector<vector<int>>&edge, vector<int>&dis, vector<int>&sum, int node = 0) {
	for (auto i : edge[node]) {
		if (dis[i] > dis[node]) {
			Search(edge, dis, sum, i);
			sum[node] += sum[i];
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> N;
	vector<long long int>ans(N,N*(N+1)/2);
	vector<vector<int>>edge(N);
	vector<int>v(N);
	for (auto &i : v) {
		cin >> i;
		i--;
	}
	EulerTour et(N, 0);
	for (int i = 1; i < N; i++) {
		cin >> L >> R;
		L--, R--;
		edge[L].push_back(R);
		edge[R].push_back(L);
		et.Add_Edge(L, R);
	}
	vector<int>dis(N, MOD);
	Calculate_Depth(edge, dis, 0);
	et.Retour();
	vector<vector<pair<int, int>>>box(N);
	for (int i = 0; i < N; i++) {
		box[v[i]].emplace_back(dis[i], i);
	}
	for (int i = 0; i < N; i++) {
		sort(box[i].begin(), box[i].end());
		reverse(box[i].begin(), box[i].end());
	}
	//for (auto i : et.tour)cout << i << " ";
	//cout << endl;
	vector<int>sum(N, 1);
	Search(edge, dis, sum);
	Add_Segment_Tree asg(et.tour.size());
	//for (auto i : sum)cout << i << " ";
	//cout << endl;
	for (int i = 0; i < N; i++) {
		//if (box[i].empty()) {
		//	ans[i] = 0;
		//	continue;
		//}
		for (auto j : box[i]) {
			int n = j.second;
			for (auto k : edge[n]) {
				if (dis[k] < dis[n])continue;
				long long int num = sum[k] - asg.Sum(et.l[k], et.r[k]) / 2;
				ans[i] -= num * (num + 1) / 2;
			}
			asg.Modify(et.l[n], et.r[n], 1);
		}
		long long int num = sum[0] - asg.Sum(et.l[0], et.r[0]) / 2;
		ans[i] -= num * (num + 1) / 2;
		asg.Modify(0, et.tour.size(), 0);
	}
	for (auto i : ans)cout << i << endl;
}

Submission Info

Submission Time
Task F - path pass i
User olphe
Language C++ (GCC 9.2.1)
Score 600
Code Size 8010 Byte
Status AC
Exec Time 1031 ms
Memory 90352 KB

Compile Error

./Main.cpp: In member function ‘void EulerTour::Retour()’:
./Main.cpp:108:21: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  108 |   for (int i = 0; i < tour.size(); i++) {
      |                   ~~^~~~~~~~~~~~~
./Main.cpp: In member function ‘void Add_Segment_Tree::Left(int)’:
./Main.cpp:125:13: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<long long int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  125 |   if (place >= v.size() / 2) {
      |       ~~~~~~^~~~~~~~~~~~~~~
./Main.cpp: In member function ‘void Add_Segment_Tree::Right(int)’:
./Main.cpp:135:13: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<long long int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  135 |   if (place >= v.size() / 2) {
      |       ~~~~~~^~~~~~~~~~~~~~~
./Main.cpp: In member function ‘long long int Add_Segment_Tree::Update(int)’:
./Main.cpp:145:13: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<long long int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  145 |   if (place >= v.size() / 2) {
      |       ~~~~~~^~~~~~~~~~~~~~~
./Main.cpp: In member function ‘void Add_Segment_Tree::Add(int, int, long long int, int)’:
./Main.cpp:176:19: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<long long int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  176 |     if (place * 2 < v.size()) {
      |         ~~~~~~~~~~^~~~~~~~~~
./Main.cpp: In member function ‘void Add_Segment_Tree::Sum(int, int, int)’:
./Main.cpp:204:19: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<long long int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  204 |     if (place * 2 < v.size()) {
      |  ...

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
AC × 5
AC × 24
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, sample_05.txt
All line_01.txt, line_3_01.txt, random_01.txt, random_02.txt, random_03.txt, random_100_01.txt, random_100_02.txt, random_10_01.txt, random_10_02.txt, random_1_01.txt, random_1_02.txt, random_2_01.txt, random_2_02.txt, random_2_03.txt, random_3_01.txt, random_3_02.txt, random_3_03.txt, sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, sample_05.txt, star_01.txt, star_3_01.txt
Case Name Status Exec Time Memory
line_01.txt AC 996 ms 90352 KB
line_3_01.txt AC 670 ms 88232 KB
random_01.txt AC 1028 ms 74668 KB
random_02.txt AC 1031 ms 74836 KB
random_03.txt AC 1024 ms 74756 KB
random_100_01.txt AC 928 ms 72636 KB
random_100_02.txt AC 917 ms 72652 KB
random_10_01.txt AC 918 ms 72984 KB
random_10_02.txt AC 911 ms 72984 KB
random_1_01.txt AC 859 ms 71944 KB
random_1_02.txt AC 868 ms 72092 KB
random_2_01.txt AC 870 ms 73208 KB
random_2_02.txt AC 888 ms 72588 KB
random_2_03.txt AC 883 ms 72728 KB
random_3_01.txt AC 904 ms 72964 KB
random_3_02.txt AC 893 ms 72860 KB
random_3_03.txt AC 903 ms 72888 KB
sample_01.txt AC 2 ms 3636 KB
sample_02.txt AC 2 ms 3680 KB
sample_03.txt AC 2 ms 3576 KB
sample_04.txt AC 2 ms 3588 KB
sample_05.txt AC 2 ms 3668 KB
star_01.txt AC 754 ms 76064 KB
star_3_01.txt AC 562 ms 74400 KB