Submission #118179

#	Time	Username	Problem	Language	Result	Execution time	Memory
118179		onjo0127	Designated Cities (JOI19_designated_cities)	C++11	7 / 100	1662 ms	94568 KiB

designated_cities

#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 = 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 (stderr)

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
• Subtask 2: 7 / 7
• Subtask 3: 0 / 9
• Subtask 4: 0 / 17
• Subtask 5: 0 / 17
• Subtask 6: 0 / 44