oj.uz

답안 #118069

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
118069 2019-06-18T06:15:59 Z 이온조(#2889) Designated Cities (JOI19_designated_cities) C++14
7 / 100
 1966 ms 125204 KB 
#include <bits/stdc++.h>
using namespace std;
using pli = pair<long long, int>;
using pii = pair<int, int>;
using tiii = tuple<int, int, int>;

const long long INF = 1LL * 1e18;

struct segtree {
	vector<long long> T, L;
	vector<int> P;
	void init(int idx, int s, int e) {
		if(s == e) {
			P[idx] = s;
			return;
		}
		int m = s+e >> 1;
		init(idx*2, s, m);
		init(idx*2+1, m+1, e);
	}
	void upd_lazy(int idx, int s, int e) {
		if(L[idx]) {
			T[idx] += L[idx];
			if(s != e) {
				L[idx*2] += L[idx];
				L[idx*2+1] += L[idx];
			}
			L[idx] = 0;
		}
	}
	pli get(int idx, int s, int e, int l, int r) {
		upd_lazy(idx, s, e);
		if(r < s || e < l) return (pli){-INF, -1};
		if(l <= s && e <= r) return (pli){T[idx], P[idx]};
		int m = s+e >> 1;
		pli L = get(idx*2, s, m, l, r), R = get(idx*2+1, m+1, e, l, r);
		if(L.first > R.first) return L;
		return R;
	}
	void upd(int idx, int s, int e, int l, int r, int v) {
		upd_lazy(idx, s, e);
		if(r < s || e < l) return;
		if(l <= s && e <= r) {
			L[idx] += v;
			upd_lazy(idx, s, e);
			return;
		}
		int m = s+e >> 1;
		upd(idx*2, s, m, l, r, v);
		upd(idx*2+1, m+1, e, l, r, v);

		T[idx] = max(T[idx*2], T[idx*2+1]);
		if(T[idx*2] > T[idx*2+1]) P[idx] = P[idx*2];
		else P[idx] = P[idx*2+1];
	}
	segtree(int sz) {
		T.resize(4*sz);
		L.resize(4*sz);
		P.resize(4*sz);
		init(1, 1, sz);
	}
};

struct MergeSortTree {
	vector<vector<int> > T;
	vector<int> get(int idx, int s, int e, int p) {
		if(p < s || e < p) return vector<int>();
		int m = s+e >> 1;
		vector<int> ret = T[idx]; //T[idx].clear();
		if(s == e) return ret;
		for(auto& it: get(idx*2, s, m, p)) ret.push_back(it);
		for(auto& it: get(idx*2+1, m+1, e, p)) ret.push_back(it);
		return ret;
	}
	void upd(int idx, int s, int e, int l, int r, int x) {
		if(r < s || e < l) return;
		if(l <= s && e <= r) {
			T[idx].push_back(x);
			return;
		}
		int m = s+e >> 1;
		upd(idx*2, s, m, l, r, x);
		upd(idx*2+1, m+1, e, l, r, x);
	}
	MergeSortTree(int sz) {
        T.resize(4*sz, vector<int>());
	}
};

vector<pii> adj[200009];
vector<tiii> itv[400009];
int in[200009], ou[200009], t;

void dfs(int x, int p) {
	in[x] = ++t;
	for(auto& it: adj[x]) {
		if(it.first != p) {
			dfs(it.first, x);
		}
	}
	ou[x] = t;
}

int main() {
	long long tot = 0;
	int N; scanf("%d",&N);
	for(int i=0; i<N-1; i++) {
		int a, b, c, d; scanf("%d%d%d%d", &a, &b, &c, &d);
		adj[a].push_back({b, c});
		adj[b].push_back({a, d});
		tot += c + d;
	}
	dfs(1, 1);

	int c = 0;
	MergeSortTree MST(N); segtree seg(N);
	for(int i=1; i<=N; i++) {
		for(auto& it: adj[i]) {
			int u = i, v = it.first, d = it.second;
			if(in[u] < in[v]) { // u is parent
				itv[++c].push_back((tiii){in[v], ou[v], d});
				MST.upd(1, 1, N, in[v], ou[v], c);
				seg.upd(1, 1, N, in[v], ou[v], d);
			}
			else { // v is parent
				itv[++c].push_back((tiii){1, in[u] - 1, d});
				itv[c].push_back((tiii){ou[u] + 1, N, d});
				MST.upd(1, 1, N, 1, in[u] - 1, c);
				MST.upd(1, 1, N, ou[u] + 1, N, c);
				seg.upd(1, 1, N, 1, in[u] - 1, d);
				seg.upd(1, 1, N, ou[u] + 1, N, d);
			}
		}
	}

	int Q; scanf("%d",&Q);
	for(int i=0; i<Q; i++) {
		int E; scanf("%d",&E);
		long long ans = tot;
		while(E--) {
			long long v; int p; tie(v, p) = seg.get(1, 1, N, 1, N);
			ans -= v;
			vector<int> er = MST.get(1, 1, N, p);
			for(auto& it: er) {
				for(auto& jt: itv[it]) {
					int l, r, v; tie(l, r, v) = jt;
					seg.upd(1, 1, N, l, r, -v);
				}
				itv[it].clear();
			}
		}
		printf("%lld\n", ans);
	}
	return 0;
}

Compilation message

designated_cities.cpp: In member function 'void segtree::init(int, int, int)':
designated_cities.cpp:17:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = s+e >> 1;
           ~^~
designated_cities.cpp: In member function 'pli segtree::get(int, int, int, int, int)':
designated_cities.cpp:35:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = s+e >> 1;
           ~^~
designated_cities.cpp: In member function 'void segtree::upd(int, int, int, int, int, int)':
designated_cities.cpp:48:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = s+e >> 1;
           ~^~
designated_cities.cpp: In member function 'std::vector<int> MergeSortTree::get(int, int, int, int)':
designated_cities.cpp:68:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = s+e >> 1;
           ~^~
designated_cities.cpp: In member function 'void MergeSortTree::upd(int, int, int, int, int, int)':
designated_cities.cpp:81:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = s+e >> 1;
           ~^~
designated_cities.cpp: In function 'int main()':
designated_cities.cpp:106:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int N; scanf("%d",&N);
         ~~~~~^~~~~~~~~
designated_cities.cpp:108:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int a, b, c, d; scanf("%d%d%d%d", &a, &b, &c, &d);
                   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
designated_cities.cpp:136:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int Q; scanf("%d",&Q);
         ~~~~~^~~~~~~~~
designated_cities.cpp:138:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int E; scanf("%d",&E);
          ~~~~~^~~~~~~~~

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 14 ms 14464 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 14464 KB Output is correct
2 Correct 1791 ms 100488 KB Output is correct
3 Correct 1642 ms 119340 KB Output is correct
4 Correct 1759 ms 105632 KB Output is correct
5 Correct 1683 ms 106220 KB Output is correct
6 Correct 1822 ms 109148 KB Output is correct
7 Correct 1621 ms 105844 KB Output is correct
8 Correct 1966 ms 125204 KB Output is correct
9 Correct 1436 ms 106656 KB Output is correct

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 14464 KB Output is correct
2 Incorrect 1761 ms 101364 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 14 ms 14464 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 14464 KB Output is correct
2 Correct 1791 ms 100488 KB Output is correct
3 Correct 1642 ms 119340 KB Output is correct
4 Correct 1759 ms 105632 KB Output is correct
5 Correct 1683 ms 106220 KB Output is correct
6 Correct 1822 ms 109148 KB Output is correct
7 Correct 1621 ms 105844 KB Output is correct
8 Correct 1966 ms 125204 KB Output is correct
9 Correct 1436 ms 106656 KB Output is correct
10 Correct 13 ms 14464 KB Output is correct
11 Incorrect 1761 ms 101364 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 14 ms 14464 KB Output isn't correct
2 Halted 0 ms 0 KB -