oj.uz

Submission #235327

# Submission time Handle Problem Language Result Execution time Memory
235327 2020-05-28T01:38:01 Z wwdd Construction of Highway (JOI18_construction) C++14
0 / 100
 6 ms 512 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pl;
typedef vector<pl> vpl;
typedef vector<int> vi;
typedef vector<vi> vvi;
const int MN = 100100;
vvi g;
vector<pl> eg;
vi po,par;
vi sub;
vi col,cop;
vvi hl;
vector<vpl> hac;
vi mac;
class ST {
	private:
	int n;
	vector<ll> st;
	public:
	ST(int _n) {n = _n;st.assign(2*n,0);}
	void up(int p, ll val) {
		p += n;
		st[p] += val;
		while(p > 1) {
			st[p>>1] = st[p]+st[p^1];
			p >>= 1;
		}
	}
	ll get(int l, int r) {
		l += n;r += n;
		ll res = 0;
		for(;l<r;l>>=1,r>>=1) {
			if(l&1) {
				res += st[l];l++;
			}
			if(r&1) {--r;
				res += st[r];
			}
		}
		return res;
	}
};
int dfa(int u, int p) {
	int res = 1;
	par[u] = p;
	for(int i=0;i<g[u].size();i++) {
		int v = g[u][i];
		if(v == p) {continue;}
		int da = dfa(v,u);
		if(mac[u] == -1 || da > sub[mac[u]]) {
			mac[u] = v;
		}
		res += da;
	}
	return sub[u] = res;
}
void dfb(int u, int p, int co) {
	cop[u] = hl[co].size();
	col[u] = co;
	hl[co].push_back(u);
	for(int i=0;i<g[u].size();i++) {
		int v = g[u][i];
		if(v == p) {continue;}
		if(v == mac[u]) {
			dfb(v,u,co);
		} else {
			int nuc = hl.size();
			hl.emplace_back();
			dfb(v,u,nuc);
		}
	}
}
int main() {
	ios::sync_with_stdio(0);cin.tie(0);
	int n;
	cin >> n;
	hl.assign(1,vi());
	mac.assign(n,-1);
	g.assign(n,vi());
	col.assign(n,-1);
	cop.assign(n,-1);
	sub.assign(n,-1);
	par.assign(n,-1);
	vector<pl> ord;
	for(int i=0;i<n;i++) {
		ll t;
		cin >> t;
		ord.push_back({t,i});
	}
	sort(ord.begin(),ord.end());
	po.assign(n,0);
	int rov = 0;
	for(int i=0;i<n;i++) {
		if(i > 0) {
			if(ord[i].first > ord[i].second) {rov = i;}
		}
		po[ord[i].second] = rov;
	}
	for(int i=1;i<n;i++) {
		int a,b;
		cin >> a >> b;
		a--;b--;
		eg.push_back({a,b});
		g[a].push_back(b);
		g[b].push_back(a);
	}
	dfa(0,0);
	dfb(0,0,0);
	/*
	for(int i=0;i<n;i++) {
		cout << po[i] << " ";
	}
	cout << '\n';
	for(int i=0;i<n;i++) {
		cout << col[i] << " ";
	}
	cout << '\n';
	*/
	hac.assign(hl.size(),vpl());
	for(int i=0;i<hl.size();i++) {
		for(int j=hl[i].size()-1;j>=0;j--) {
			int u = hl[i][j];
			hac[i].push_back({po[u],1});
		}
	}
	ST st(n);
	for(int idx=0;idx<eg.size();idx++) {
		vector<pl> ok;
		int u = eg[idx].first;
		int rep = po[eg[idx].second];
		while(1) {
			int rs = 0;
			int co = col[u];
			int rec = cop[u]+1;
			stack<pl> te;
			while(rs < rec) {
				pl wa = hac[co].back();hac[co].pop_back();
				if(rs+wa.second > rec) {
					hac[co].push_back({wa.first,wa.second+rs-rec});
					wa.second = rec-rs;
				}
				te.push(wa);
				rs += wa.second;
			}
			hac[co].push_back({rep,rec});
			u = hl[col[u]][0];
			while(!te.empty()) {ok.push_back(te.top());te.pop();}
			if(u == 0) {break;}
			u = par[u];
		}
		ll res = 0;
		for(int i=0;i<ok.size();i++) {
			int num = ok[i].second;
			int pv = ok[i].first;
			res += st.get(0,pv)*num;
			st.up(pv,num);
		}
		for(int i=0;i<ok.size();i++) {
			int num = ok[i].second;
			int pv = ok[i].first;
			st.up(pv,-num);
		}
		cout << res << '\n';
	}
}

Compilation message

construction.cpp: In function 'int dfa(int, int)':
construction.cpp:48:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[u].size();i++) {
              ~^~~~~~~~~~~~
construction.cpp: In function 'void dfb(int, int, int)':
construction.cpp:63:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[u].size();i++) {
              ~^~~~~~~~~~~~
construction.cpp: In function 'int main()':
construction.cpp:122:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<hl.size();i++) {
              ~^~~~~~~~~~
construction.cpp:129:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int idx=0;idx<eg.size();idx++) {
                ~~~^~~~~~~~~~
construction.cpp:154:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<ok.size();i++) {
               ~^~~~~~~~~~
construction.cpp:160:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<ok.size();i++) {
               ~^~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 6 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 512 KB Output is correct
9 Correct 5 ms 512 KB Output is correct
10 Correct 5 ms 512 KB Output is correct
11 Correct 5 ms 512 KB Output is correct
12 Correct 6 ms 512 KB Output is correct
13 Correct 5 ms 512 KB Output is correct
14 Correct 5 ms 512 KB Output is correct
15 Incorrect 6 ms 384 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 6 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 512 KB Output is correct
9 Correct 5 ms 512 KB Output is correct
10 Correct 5 ms 512 KB Output is correct
11 Correct 5 ms 512 KB Output is correct
12 Correct 6 ms 512 KB Output is correct
13 Correct 5 ms 512 KB Output is correct
14 Correct 5 ms 512 KB Output is correct
15 Incorrect 6 ms 384 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 84.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 6 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 512 KB Output is correct
9 Correct 5 ms 512 KB Output is correct
10 Correct 5 ms 512 KB Output is correct
11 Correct 5 ms 512 KB Output is correct
12 Correct 6 ms 512 KB Output is correct
13 Correct 5 ms 512 KB Output is correct
14 Correct 5 ms 512 KB Output is correct
15 Incorrect 6 ms 384 KB Output isn't correct
16 Halted 0 ms 0 KB -