oj.uz

Submission #376159

# Submission time Handle Problem Language Result Execution time Memory
376159 2021-03-11T02:22:22 Z casperwang Designated Cities (JOI19_designated_cities) C++14
16 / 100
 972 ms 82504 KB 
#include <bits/stdc++.h>
#define int long long
#define pb emplace_back
#define pii pair<int,int>
#define ff first
#define ss second
using namespace std;
#define debug(args...) kout("[ " + string(#args) + " ]", args)
void kout() { cerr << endl; }
template <class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ',kout(b...); }
template <class T> void pary(T L, T R) { while (L != R) cerr << *L << " \n"[++L==R]; }

struct Edge {
	int to, val;
	Edge(int t, int v) {
		to = t, val = v;
	}
};

const int MAXN = 200000;
const int INF = 1e18;
int N, Q;
int a, b, c, d;
vector <int> path[MAXN+1];
vector <Edge> E;
pii dfs[MAXN+1];
int ord[MAXN*2+1];
int cnt;
int dis[MAXN+1];
int ans[MAXN+1];
int cal;

class Seg {
	private:
		int arr[MAXN*8+5];
		int tag[MAXN*8+5];
		void pull(int now) {
			arr[now] = max(arr[now*2], arr[now*2+1]);
		}
		void push(int now, int len) {
			if (!tag[now]) return;
			arr[now] += tag[now];
			if (len > 1) {
				tag[now*2  ] += tag[now];
				tag[now*2+1] += tag[now];
			}
			tag[now] = 0;
		}
	public:
		void build(int now=1, int l=1, int r=2*N) {
			if (l == r) {
				arr[now] = dis[ord[l]];
				return;
			}
			int mid = l + r >> 1;
			build(now*2  , l, mid);
			build(now*2+1,mid+1,r);
			pull(now);
		}
		void mdy(int ml, int mr, int k, int now=1, int l=1, int r=2*N) {
			push(now, r-l+1);
			if (ml <= l && r <= mr) {
				tag[now] += k;
				push(now, r-l+1);
				return;
			} else if (l > mr || r < ml) return;
			int mid = l + r >> 1;
			mdy(ml, mr, k, now*2  , l, mid);
			mdy(ml, mr, k, now*2+1,mid+1,r);
			pull(now);
		}
		int qry() {
			return arr[1];
		}
} seg;

void dfs_init(int now, int par) {
	dfs[now].ff = ++cnt;
	ord[cnt] = now;
	for (int id : path[now]) {
		Edge e = E[id];
		if (e.to == par) continue;
		dis[e.to] = dis[now] + e.val;
		cal += e.val;
		dfs_init(e.to, now);
	}
	dfs[now].ss = ++cnt;
	ord[cnt] = now;
}

void dfs_1(int now, int par) {
	ans[1] = min(ans[1], cal);
	for (int id : path[now]) {
		Edge e = E[id], re = E[id^1];
		if (e.to == par) continue;
		cal += re.val - e.val;
		dfs_1(e.to, now);
		cal -= re.val - e.val;
	}
}

void dfs_2(int now, int par) {
	ans[2] = min(ans[2], cal - seg.qry());
	for (int id : path[now]) {
		Edge e = E[id], re = E[id^1];
		if (e.to == par) continue;
		cal += re.val - e.val;
		seg.mdy(dfs[e.to].ff, dfs[e.to].ss, -e.val);
		seg.mdy(1, dfs[e.to].ff, re.val);
		seg.mdy(dfs[e.to].ss, 2*N, re.val);
		dfs_2(e.to, now);
		cal -= re.val - e.val;
		seg.mdy(dfs[e.to].ff, dfs[e.to].ss, e.val);
		seg.mdy(1, dfs[e.to].ff, -re.val);
		seg.mdy(dfs[e.to].ss, 2*N, -re.val);
	}
}

void solve() {
	cal = 0;
	dfs_init(1, 0);
	dfs_1(1, 0);
	seg.build();
	dfs_2(1, 0);
}

signed main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> N;
	for (int i = 1; i < N; i++) {
		cin >> a >> b >> c >> d;
		path[a].pb(E.size());
		E.pb(b, c);
		path[b].pb(E.size());
		E.pb(a, d);
		ans[i] = INF;
	}
	solve();
	cin >> Q;
	for (int i = 1; i <= Q; i++) {
		cin >> a;
		cout << ans[a] << '\n';
	}
}

Compilation message

designated_cities.cpp: In member function 'void Seg::build(long long int, long long int, long long int)':
designated_cities.cpp:55:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   55 |    int mid = l + r >> 1;
      |              ~~^~~
designated_cities.cpp: In member function 'void Seg::mdy(long long int, long long int, long long int, long long int, long long int, long long int)':
designated_cities.cpp:67:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   67 |    int mid = l + r >> 1;
      |              ~~^~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Incorrect 4 ms 5100 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 778 ms 45736 KB Output is correct
3 Correct 972 ms 72680 KB Output is correct
4 Correct 747 ms 45640 KB Output is correct
5 Correct 751 ms 45816 KB Output is correct
6 Correct 823 ms 49608 KB Output is correct
7 Correct 723 ms 45768 KB Output is correct
8 Correct 953 ms 73416 KB Output is correct
9 Correct 640 ms 46152 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5100 KB Output is correct
2 Correct 769 ms 45128 KB Output is correct
3 Correct 964 ms 82504 KB Output is correct
4 Correct 779 ms 49700 KB Output is correct
5 Correct 748 ms 50996 KB Output is correct
6 Correct 821 ms 55296 KB Output is correct
7 Correct 602 ms 51144 KB Output is correct
8 Correct 881 ms 68296 KB Output is correct
9 Correct 577 ms 51072 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Incorrect 4 ms 5100 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 778 ms 45736 KB Output is correct
3 Correct 972 ms 72680 KB Output is correct
4 Correct 747 ms 45640 KB Output is correct
5 Correct 751 ms 45816 KB Output is correct
6 Correct 823 ms 49608 KB Output is correct
7 Correct 723 ms 45768 KB Output is correct
8 Correct 953 ms 73416 KB Output is correct
9 Correct 640 ms 46152 KB Output is correct
10 Correct 5 ms 5100 KB Output is correct
11 Correct 769 ms 45128 KB Output is correct
12 Correct 964 ms 82504 KB Output is correct
13 Correct 779 ms 49700 KB Output is correct
14 Correct 748 ms 50996 KB Output is correct
15 Correct 821 ms 55296 KB Output is correct
16 Correct 602 ms 51144 KB Output is correct
17 Correct 881 ms 68296 KB Output is correct
18 Correct 577 ms 51072 KB Output is correct
19 Correct 4 ms 5100 KB Output is correct
20 Incorrect 775 ms 50864 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Incorrect 4 ms 5100 KB Output isn't correct
3 Halted 0 ms 0 KB -