oj.uz

Submission #118183

# Submission time Handle Problem Language Result Execution time Memory
118183 2019-06-18T10:19:57 Z onjo0127 Designated Cities (JOI19_designated_cities) C++11
16 / 100
 1865 ms 93912 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> evt[200009], 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);
                evt[in[v]].push_back({+1, c});
                evt[ou[v]+1].push_back({-1, c});
            }
            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);
                evt[1].push_back({+1, c});
                evt[in[u]].push_back({-1, c});
                evt[ou[u] + 1].push_back({+2, c});
            }
        }
    }

    int Q; scanf("%d",&Q);
    if(Q == 1) {
        segtree X = seg;
        int E; scanf("%d",&E);
        if(E == 1) return !printf("%lld", tot - seg.get(1, 1, N, 1, N).first);
        if(E == 2) {
            long long ans = 0;
            for(int i=1; i<=N; i++) {
                for(auto& it: evt[i]) {
                    int ty, n; tie(ty, n) = it;
                    for(auto& it: itv[n]) {
                        int l, r, v; tie(l, r, v) = it;
                        if(ty > 0) X.upd(1, 1, N, l, r, -v);
                        else X.upd(1, 1, N, l, r, +v);
                    }
                }
                ans = max(ans, seg.get(1, 1, N, i, i).first + X.get(1, 1, N, 1, N).first);
            }
            printf("%lld", tot - ans);
        }
    }

	/*
	int Q; scanf("%d",&Q);
	for(int i=0; i<Q; i++) {
		int E; scanf("%d",&E);
		int l = 0, r = 1e9; long long f;
		for(int m=0; m<=100; m++) {
            //int m = l+r >> 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);
                        printf("interval: %d %d %d\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);
                        printf("interval: %d %d %d\n", ou[u]+1, in[u]-1, d);
                    }
                }
            }

            int nk = 0;
            long long lans = 0;
            while(1) {
                long long v; int p; tie(v, p) = seg.get(1, 1, N, 1, N); v -= m;
                printf("v: %lld, p: %d\n", v, p);
                if(v <= 0) break;
                lans += v; ++nk;
                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();
                }
            }

            for(int i=1; i<=c; i++) itv[i].clear();

            printf("m: %d, nk: %d, lans: %lld\n", m, nk, lans + nk*m);

            if(nk <= E) r = m-1, f = lans + E*m;
            else l = m+1;
        }
		printf("%lld\n", tot - f);
	}
	*/
	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:141:17: 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:144:21: 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 Incorrect 18 ms 19072 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 19072 KB Output is correct
2 Correct 1020 ms 84032 KB Output is correct
3 Correct 922 ms 89556 KB Output is correct
4 Correct 966 ms 83992 KB Output is correct
5 Correct 969 ms 83956 KB Output is correct
6 Correct 1029 ms 85140 KB Output is correct
7 Correct 843 ms 83816 KB Output is correct
8 Correct 1273 ms 91368 KB Output is correct
9 Correct 821 ms 83492 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 19064 KB Output is correct
2 Correct 1673 ms 84184 KB Output is correct
3 Correct 1346 ms 93912 KB Output is correct
4 Correct 1713 ms 87132 KB Output is correct
5 Correct 1683 ms 86876 KB Output is correct
6 Correct 1784 ms 88120 KB Output is correct
7 Correct 1493 ms 86604 KB Output is correct
8 Correct 1865 ms 91528 KB Output is correct
9 Correct 1425 ms 86568 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 19072 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 19072 KB Output is correct
2 Correct 1020 ms 84032 KB Output is correct
3 Correct 922 ms 89556 KB Output is correct
4 Correct 966 ms 83992 KB Output is correct
5 Correct 969 ms 83956 KB Output is correct
6 Correct 1029 ms 85140 KB Output is correct
7 Correct 843 ms 83816 KB Output is correct
8 Correct 1273 ms 91368 KB Output is correct
9 Correct 821 ms 83492 KB Output is correct
10 Correct 18 ms 19064 KB Output is correct
11 Correct 1673 ms 84184 KB Output is correct
12 Correct 1346 ms 93912 KB Output is correct
13 Correct 1713 ms 87132 KB Output is correct
14 Correct 1683 ms 86876 KB Output is correct
15 Correct 1784 ms 88120 KB Output is correct
16 Correct 1493 ms 86604 KB Output is correct
17 Correct 1865 ms 91528 KB Output is correct
18 Correct 1425 ms 86568 KB Output is correct
19 Correct 17 ms 19072 KB Output is correct
20 Incorrect 1063 ms 86932 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 19072 KB Output isn't correct
2 Halted 0 ms 0 KB -