oj.uz

Submission #105925

# Submission time Handle Problem Language Result Execution time Memory
105925 2019-04-15T17:56:16 Z Kepperoni Designated Cities (JOI19_designated_cities) C++14
0 / 100
 1847 ms 61280 KB 
#include <bits/stdc++.h>
#define x first
#define y second
#define pb push_back

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int MAXN = 2e5 + 10;

int n;
map<pii, ll> ma;
vector<int> k[MAXN];
int root = 1;
int cfr[MAXN], cto[MAXN], wh[MAXN];
ll ans[MAXN];
int par[MAXN];
bool vis[MAXN];

ll lz[MAXN*4], sum[MAXN*4], wma[MAXN*4];

void prop(int v){
	if(lz[v] != 0){
		sum[v] += lz[v];
		lz[v*2] += lz[v];
		lz[v*2+1] += lz[v];
		lz[v] = 0;
	}
}

void init(int v, int le, int ri){
	wma[v] = wh[le];
	if(le != ri){
		int mid = (le+ri)/2;
		init(v*2, le, mid);
		init(v*2+1, mid+1, ri);
	}
}

void ch(int v, int le, int ri, int fr, int to, ll mucho){
	prop(v);
	//cout << le << " " << ri << " " << fr << " " << to << endl;
	if(ri < fr || le > to) return;
	else if(fr <= le && ri <= to){
		lz[v] += mucho;
		prop(v);
		return;
	}

	ch(v*2, le, (le+ri)/2, fr, to, mucho);
	ch(v*2+1, (le+ri)/2+1, ri, fr, to, mucho);

	if(sum[v*2] > sum[v*2+1]) sum[v] = sum[v*2], wma[v] = wma[v*2];
	else sum[v] = sum[v*2+1], wma[v] = wma[v*2+1];
}


int ctim = 1;
void dfs(int v, int p = 0){
	par[v] = p;
	wh[ctim] = v;
	cfr[v] = ctim++;

	for(auto x : k[v])
		if(x != p)
			dfs(x, v);

	cto[v] = ctim-1;
}

ll locans[MAXN];
void srch(int v, ll cu, int p=0){
	//cout << v << " " << cu << endl;
	locans[v] = cu;
	for(auto x : k[v])
		if(x != p)
			srch(x, cu - ma[pii(v, x)] + ma[pii(x, v)], v);
}

int main(){
	scanf(" %d", &n);
	for(int i=1; i<n; i++){
		int ca, cb, cc, cd; scanf(" %d %d %d %d", &ca, &cb, &cc, &cd);
		ma[pii(ca, cb)] = cc;
		ma[pii(cb, ca)] = cd;
		k[ca].pb(cb);
		k[cb].pb(ca);
	}

	if(k[root].size() == 1)
		for(auto x : k[root])
			if(k[x].size() != 1){
				root = x;
				break;
			}
		
	dfs(root);
	
	init(1, 1, n);
	
	ll curpay = 0;
	for(int i=1; i<=n; i++)
		if(par[i] != 0){
			curpay += ma[pii(par[i], i)];
			ch(1, 1, n, cfr[i], cto[i], ma[pii(par[i], i)]);
		}
	
	srch(root, curpay);

	for(int i=1; i<=n; i++){
		prop(1);
		if(curpay != 0){
			int cans = wma[1];
			curpay -= sum[1];

			while(cans != 1 && !vis[cans]){
				vis[cans] = true;
				ch(1, 1, n, cfr[cans], cto[cans], -ma[pii(par[cans], cans)]);
				cans = par[cans];
			}

			ans[i] = curpay;
		}
	}

	ans[1] = 1e16;
	for(int i=1; i<=n; i++) ans[1] = min(ans[1], locans[i]);

	int q; scanf(" %d", &q);
	while(q--){
		int e; scanf(" %d", &e);
		printf("%lld\n", ans[e]);
	}
}

Compilation message

designated_cities.cpp: In function 'int main()':
designated_cities.cpp:83:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf(" %d", &n);
  ~~~~~^~~~~~~~~~~
designated_cities.cpp:85:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int ca, cb, cc, cd; scanf(" %d %d %d %d", &ca, &cb, &cc, &cd);
                       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
designated_cities.cpp:131: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:133: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

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5120 KB Output is correct
2 Correct 7 ms 5120 KB Output is correct
3 Correct 9 ms 5120 KB Output is correct
4 Incorrect 6 ms 5120 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5120 KB Output is correct
2 Incorrect 1764 ms 61168 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5120 KB Output is correct
2 Incorrect 1847 ms 61280 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5120 KB Output is correct
2 Correct 7 ms 5120 KB Output is correct
3 Correct 9 ms 5120 KB Output is correct
4 Incorrect 6 ms 5120 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5120 KB Output is correct
2 Incorrect 1764 ms 61168 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5120 KB Output is correct
2 Correct 7 ms 5120 KB Output is correct
3 Correct 9 ms 5120 KB Output is correct
4 Incorrect 6 ms 5120 KB Output isn't correct
5 Halted 0 ms 0 KB -