Submission #105849

#	Time	Username	Problem	Language	Result	Execution time	Memory
105849		Pro_ktmr	Designated Cities (JOI19_designated_cities)	C++14	6 / 100	1726 ms	5400 KiB

designated_cities

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#include"bits/stdc++.h"
using namespace std;
#define LL long long
#define MP make_pair
#define PB push_back

#define int long long

struct UnionFind{
private:
	int N;
	vector<int> par;
public:
	void init(int n){
		N = n;
		par.clear();
		for(int i=0; i<N; i++) par.PB(i);
	}
	int root(int a){
		if(par[a] == a) return a;
		return par[a] = root(par[a]);
	}
	void unite(int a, int b){
		a = root(a);
		b = root(b);
		if(a != b) par[b] = a;
	}
	bool same(int a, int b){
		return (root(a) == root(b));
	}
};

//RmaxQ RAD
struct SegmentTree{
private:
	int N;
	vector<LL> node,lazy;
public:
	void init(int n){
		N = 1;
		while(N < n) N *= 2;
		node.clear();
		for(int i=0; i<2*N-1; i++) node.PB(0LL);
		lazy.clear();
		for(int i=0; i<2*N-1; i++) lazy.PB(0LL);
	}
	void eval(int k, int l, int r){
		if(lazy[k] == 0LL) return;
		node[k] += lazy[k];
		if(r-l != 1){
			lazy[2*k+1] += lazy[k];
			lazy[2*k+2] += lazy[k];
		}
		lazy[k] = 0;
	}
	void update(int k, LL x){
		k += N-1;
		node[k] = max(node[k], x);
		while(k > 0){
			k = (k-1)/2;
			node[k] = max(node[k], x);
		}
	}
	void add(int a, int b, LL x, int k=0, int l=0, int r=-1){
		if(r == -1) r = N;
		if(r <= a || b <= l) return;
		if(a <= l && r <= b){
			lazy[k] += x;
			eval(k, l, r);
		}
		else{
			eval(k, l, r);
			add(a, b, x, 2*k+1, l, (l+r)/2);
			add(a, b, x, 2*k+2, (l+r)/2, r);
			node[k] = max(node[2*k+1], node[2*k+2]);
		}
	}
	pair<LL,int> maximum(int a, int b, int k=0, int l=0, int r=-1){
		if(r == -1) r = N;
		eval(k, l, r);
		if(r <= a || b <= l) return MP(-1,-1);
		if(r-l == 1) return MP(node[k], k-(N-1));
		if(a <= l && r <= b){
			eval(2*k+1, l, (l+r)/2);
			eval(2*k+2, (l+r)/2, r);
			if(node[2*k+1] > node[2*k+2]) return maximum(a, b, 2*k+1, l, (l+r)/2);
			else return maximum(a, b, 2*k+2, (l+r)/2, r);
		}
		else return max(maximum(a, b, 2*k+1, l, (l+r)/2), maximum(a, b, 2*k+2, (l+r)/2, r));
	}
	void print(){
		for(int i=0; i<2*N-1; i++) cout << node[i] << " ";
		cout << endl;
		for(int i=0; i<2*N-1; i++) cout << lazy[i] << " ";
		cout << endl;
	}
};

int N,Q;
vector<pair<int,LL>> edge[200000];
LL all = 0;
LL ans[200001];

bool visit[200000] = {};
int par[200000] = {};
int parCost[200000] = {};
int pos[200000] = {};
int c;
LL sum;
SegmentTree st;
void dfs(int now, LL cost, int bef){
	visit[now] = true;
	par[c] = bef;
	st.update(c, cost);
	int dfs_order = c;
	c++;
	for(int i=0; i<edge[now].size(); i++){
		if(visit[edge[now][i].first]) continue;
		sum += edge[now][i].second;
		parCost[c] = edge[now][i].second;
		dfs(edge[now][i].first, cost + edge[now][i].second, dfs_order);
	}
	pos[dfs_order] = c;
}

UnionFind uf;

signed main(){
	scanf("%lld", &N);
	if(N > 2000) return -1;
	for(int i=0; i<N-1; i++){
		int A,B,C,D;
		scanf("%lld%lld%lld%lld", &A, &B, &C, &D);
		A--; B--;
		edge[A].PB(MP(B,C));
		edge[B].PB(MP(A,D));
		all += C+D;
	}
	for(int i=1; i<=N; i++) ans[i] = LLONG_MAX;
	
	//root doko
	for(int i=0; i<N; i++){
		for(int j=0; j<N; j++) visit[j] = false;
		c = 0;
		st.init(N);
		uf.init(N);
		sum = 0;
		dfs(i,0, -1);
		//st.print();
		ans[1] = min(ans[1], sum);
		//cout << sum << " ";
		for(int j=2; j<=N; j++){
			pair<LL,int> tmp = st.maximum(0, N);
			sum -= tmp.first;
			ans[j] = min(ans[j], sum);
			//cout << sum << " ";
			int now = tmp.second;
			now = uf.root(now);
			while(now != 0){
				st.add(now, pos[now], -parCost[now]);
				uf.unite(par[now], now);
				now = uf.root(now);
			}
		}
		//cout << endl;
	}
	
	scanf("%lld", &Q);
	for(int i=0; i<Q; i++){
		int E;
		scanf("%lld", &E);
		printf("%lld\n", ans[E]);
	}
	
	return 0;
}

Compilation message (stderr)

designated_cities.cpp: In function 'void dfs(long long int, long long int, long long int)':
designated_cities.cpp:121:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<edge[now].size(); i++){
               ~^~~~~~~~~~~~~~~~~
designated_cities.cpp: In function 'int main()':
designated_cities.cpp:133:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld", &N);
  ~~~~~^~~~~~~~~~~~
designated_cities.cpp:137:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld%lld%lld", &A, &B, &C, &D);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
designated_cities.cpp:172:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld", &Q);
  ~~~~~^~~~~~~~~~~~
designated_cities.cpp:175:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &E);
   ~~~~~^~~~~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 0 / 7
• Subtask 3: 0 / 9
• Subtask 4: 0 / 17
• Subtask 5: 0 / 17
• Subtask 6: 0 / 44