답안 #82502 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
82502	2018-10-31T07:18:18 Z	wzy	Construction of Highway (JOI18_construction)	C++11	0 / 100	88 ms	70764 KB

construction

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define F first
#define S second
#define mp make_pair
#define pb push_back
const int N = 100005; 
int sz[N] , in[N] , out[N] , C[N], t = 0 , ch[N] , depth[N] , inv[N] , pai[N] , endch[N];
vector<int> adj[N];
int n;
vector<pii> edge;
vector<pii> cor;
void dfs(int x , int y){
	sz[x] = 1;
	depth[x] = 0;
	depth[x] = depth[y] + 1;
	pai[x] = -1;
	if(x != y) pai[x] = y;
	for(auto &p : adj[x]){
		if(p == y) continue;
		dfs(p,x);
		sz[x] += sz[p];
		if(adj[x][0] == y || sz[p] >= sz[adj[x][0]]) swap(p, adj[x][0]);
	}
}

int dfs_hld(int x, int y){
	in[x] = ++t;
	inv[in[x]] = x;
	endch[ch[x]] = x;
	for(auto p : adj[x]){
		if(p == y) continue;
		if(p == adj[x][0]) ch[p] = ch[x];
		else ch[p] = p;
		dfs_hld(p , x);
	}
	out[x] = t;
}



map<int,int> ordi;
set<int> sorti;

int BIT[N + 100];

void add(int x , int v){
	for(int i = x ; i < (N + 100) ; i += (i&-i)) BIT[i] += v;
}

int get(int x){
	int s = 0;
	for(int i = x ; i > 0 ; i-= (i&-i)){
		s += BIT[i];
	}
	return s;
}
deque< array<int, 4> > cs[N + 100];

int32_t main(){
	scanf("%d" , &n);
	for(int i = 1 ; i <= n; i ++) scanf("%d" , &C[i]) , sorti.insert(C[i]);
	int CC = 0;
	for(auto p : sorti){
		ordi[p] = ++CC;
	}
	for(int i = 1 ; i <= n; i ++){
		C[i] = ordi[C[i]];
	}
	for(int i = 1 ; i < n ;i ++){
		int x , y;
		scanf("%d%d" , &x , &y);
		adj[x].pb(y);
		adj[y].pb(x);
		edge.push_back(pii(x,y));
	}
	ch[1] = 1;
	dfs(1,1);
	dfs_hld(1,1);
	ch[1] = 1 , pai[1] = -1;
	array<int, 4> ux;
	ux[0] = in[1] , ux[1] = in[1] , ux[2] = C[1] , ux[3] = 1;
	cs[ch[1]].push_back(ux);
	for(auto p : edge){
		vector<pii> q;
		int X = p.F;
		while(X != -1){
			int l = 0 , r = cs[ch[X]].size();
			r--;
			int ansj = -1;
			while(l<=r){
				int mid = (l+r)/2;
				if(cs[ch[X]][mid][0] <= in[X]){
					ansj = mid;
					l = mid + 1;
				}
				else
				r = mid - 1;
			}
			if(ansj != -1){
				q.push_back(pii(cs[ch[X]][ansj][1+1], in[X] - cs[ch[X]][ansj][0] + 1));
			}
			for(int i = ansj - 1 ; i >= 0 ; i--){
				q.push_back(pii(cs[ch[X]][i][1+1] , cs[ch[X]][i][2+1]));
			}
			X = pai[ch[X]];
		}
		reverse(q.begin() , q.end());
		long long ans = 0;
		for(auto w : q){
			add(w.F , w.S);
			int U = get(CC + 2) - get(w.F);
			long long P = U;
			P *= w.S;
			ans += P;
		}
		for(auto w : q){
			add(w.F , -w.S);
		}
		X = p.S;
		while(X != -1){
			array<int, 4> ux;
			ux[0] = in[ch[X]] , ux[1] = in[X] , ux[2] = C[p.S] , ux[3] = 0;
			if(X == p.S) ux[3]++;
			while(cs[ch[X]].size() && cs[ch[X]].front()[1] <= in[X]) ux[3] += cs[ch[X]].front()[3] , cs[ch[X]].pop_front();
			if(cs[ch[X]].size() && cs[ch[X]].front()[0] <= in[X]){
				int R = in[X] - cs[ch[X]].front()[0] + 1;
				cs[ch[X]].front()[3] -= R;
				cs[ch[X]].front()[0] = in[adj[X][0]];
				ux[3] += R;
			}
			while(cs[ch[X]].size() && cs[ch[X]].front()[2] == C[p.S]) ux[3] += cs[ch[X]].front()[3] , cs[ch[X]].pop_front();
			cs[ch[X]].push_front(ux);
			for(auto px : cs[ch[X]]){
				//cout<<X<<" " << p.F<<" "<<p.S<<" " << px[0]<<" " <<px[1] <<" " << px[2] << " " << px[3] << endl;
			}
			X = pai[ch[X]];
		}
		printf("%lld\n" , ans);
	}

}
/* 
10
1 7 3 4 8 6 2 9 10 5
1 2
1 3
2 4
3 5
2 6
3 7
4 8
5 9
6 10
*/

Compilation message

construction.cpp: In function 'int dfs_hld(int, int)':
construction.cpp:39:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
construction.cpp: In function 'int32_t main()':
construction.cpp:135:13: warning: variable 'px' set but not used [-Wunused-but-set-variable]
    for(auto px : cs[ch[X]]){
             ^~
construction.cpp:62:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d" , &n);
  ~~~~~^~~~~~~~~~~
construction.cpp:63:52: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 1 ; i <= n; i ++) scanf("%d" , &C[i]) , sorti.insert(C[i]);
                                ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
construction.cpp:73:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d" , &x , &y);
   ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	68 ms	70136 KB	Output is correct
2	Correct	68 ms	70312 KB	Output is correct
3	Correct	75 ms	70436 KB	Output is correct
4	Correct	85 ms	70536 KB	Output is correct
5	Correct	73 ms	70536 KB	Output is correct
6	Correct	74 ms	70536 KB	Output is correct
7	Correct	74 ms	70568 KB	Output is correct
8	Correct	70 ms	70568 KB	Output is correct
9	Correct	74 ms	70568 KB	Output is correct
10	Correct	75 ms	70568 KB	Output is correct
11	Correct	80 ms	70604 KB	Output is correct
12	Correct	82 ms	70604 KB	Output is correct
13	Correct	73 ms	70604 KB	Output is correct
14	Correct	84 ms	70608 KB	Output is correct
15	Correct	84 ms	70608 KB	Output is correct
16	Correct	77 ms	70624 KB	Output is correct
17	Correct	82 ms	70644 KB	Output is correct
18	Correct	74 ms	70644 KB	Output is correct
19	Correct	88 ms	70644 KB	Output is correct
20	Correct	71 ms	70644 KB	Output is correct
21	Correct	80 ms	70764 KB	Output is correct
22	Incorrect	82 ms	70764 KB	Output isn't correct
23	Halted	0 ms	0 KB	-

Subtask #2
0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	68 ms	70136 KB	Output is correct
2	Correct	68 ms	70312 KB	Output is correct
3	Correct	75 ms	70436 KB	Output is correct
4	Correct	85 ms	70536 KB	Output is correct
5	Correct	73 ms	70536 KB	Output is correct
6	Correct	74 ms	70536 KB	Output is correct
7	Correct	74 ms	70568 KB	Output is correct
8	Correct	70 ms	70568 KB	Output is correct
9	Correct	74 ms	70568 KB	Output is correct
10	Correct	75 ms	70568 KB	Output is correct
11	Correct	80 ms	70604 KB	Output is correct
12	Correct	82 ms	70604 KB	Output is correct
13	Correct	73 ms	70604 KB	Output is correct
14	Correct	84 ms	70608 KB	Output is correct
15	Correct	84 ms	70608 KB	Output is correct
16	Correct	77 ms	70624 KB	Output is correct
17	Correct	82 ms	70644 KB	Output is correct
18	Correct	74 ms	70644 KB	Output is correct
19	Correct	88 ms	70644 KB	Output is correct
20	Correct	71 ms	70644 KB	Output is correct
21	Correct	80 ms	70764 KB	Output is correct
22	Incorrect	82 ms	70764 KB	Output isn't correct
23	Halted	0 ms	0 KB	-

Subtask #3
0 / 84.0

#	결과	실행 시간	메모리	Grader output
1	Correct	68 ms	70136 KB	Output is correct
2	Correct	68 ms	70312 KB	Output is correct
3	Correct	75 ms	70436 KB	Output is correct
4	Correct	85 ms	70536 KB	Output is correct
5	Correct	73 ms	70536 KB	Output is correct
6	Correct	74 ms	70536 KB	Output is correct
7	Correct	74 ms	70568 KB	Output is correct
8	Correct	70 ms	70568 KB	Output is correct
9	Correct	74 ms	70568 KB	Output is correct
10	Correct	75 ms	70568 KB	Output is correct
11	Correct	80 ms	70604 KB	Output is correct
12	Correct	82 ms	70604 KB	Output is correct
13	Correct	73 ms	70604 KB	Output is correct
14	Correct	84 ms	70608 KB	Output is correct
15	Correct	84 ms	70608 KB	Output is correct
16	Correct	77 ms	70624 KB	Output is correct
17	Correct	82 ms	70644 KB	Output is correct
18	Correct	74 ms	70644 KB	Output is correct
19	Correct	88 ms	70644 KB	Output is correct
20	Correct	71 ms	70644 KB	Output is correct
21	Correct	80 ms	70764 KB	Output is correct
22	Incorrect	82 ms	70764 KB	Output isn't correct
23	Halted	0 ms	0 KB	-

답안 #82502

Compilation message

Subtask #1 0 / 7.0

Subtask #2 0 / 9.0

Subtask #3 0 / 84.0

Subtask #1
0 / 7.0

Subtask #2
0 / 9.0

Subtask #3
0 / 84.0