Submission #522401

#	Time	Username	Problem	Language	Result	Execution time	Memory
522401		lukameladze	Designated Cities (JOI19_designated_cities)	C++14	100 / 100	826 ms	76072 KiB

designated_cities

# include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define int long long
#define pii pair <int, int>
using namespace std;
const int N = 3e5 + 5;
int t,n,a[N],in[N],out[N],lv[N],sum,tin,b[N],c[N],d[N],up[N],vert,ver[N];
int fix[N],par[N];
int ans[N];

vector <pair <int , pii > > v[N];
struct nod{
    int idx;
    int mx;
};
nod tree[4*N],emp;
int lazy[4*N]; 
nod merge(nod a, nod b) {
    if (a.mx >= b.mx) return a;
    else return b;
}
void build(int node, int le, int ri) {
    lazy[node] = 0;
    if (le == ri) {
        tree[node].idx = le;
        tree[node].mx = 0;
        return ;
    }
    int mid = (le + ri) / 2;
    build(2*node,le,mid);
    build(2*node + 1, mid + 1, ri);
    tree[node] = merge(tree[2*node], tree[2*node + 1]);
}
void update(int node,int le,int ri,int start,int end,int val) {
	if(lazy[node]) {
		tree[node].mx += lazy[node];
		if(le != ri) {
			lazy[2*node] += lazy[node];
			lazy[2*node+1] += lazy[node];
		}
		lazy[node]=0;
	}
	if(le>end || ri<start) 
	return;
	if(start <= le && ri <= end) {
		tree[node].mx += val;
		if(le != ri) {
			lazy[2*node] += val;
			lazy[2*node+1] += val;
		}
		return;
	}
	int mid = (le + ri) / 2;
	update(2*node,le,mid,start,end,val);
	update(2*node+1,mid+1,ri,start,end,val);
	tree[node] = merge(tree[2*node], tree[2*node+1]);
}
nod getans(int node,int le,int ri,int start,int end) {
	if(lazy[node]) {
		tree[node].mx += lazy[node];
		if(le != ri) {
			lazy[2*node] += lazy[node];
			lazy[2*node+1] += lazy[node];
		}
		lazy[node] = 0;
	}
	if(le > end || ri < start) return emp;
	if(start <= le && ri <= end) {
		return tree[node];
	}
	int mid=( le + ri) / 2;
	return merge(getans(2*node,le,mid,start,end), getans(2*node+1,mid+1,ri,start,end));
}
void dfs(int a, int p,int cost, int cost1) {
    tin++;
    in[a] = tin;
    ver[in[a]] = a;
    //rootidan a shi rom chamoxvide
    par[a] = p;
    up[a] = cost;
    sum += cost;
    lv[a] = lv[p] + cost;
    if (vert) {
        if (v[a].size() == 1 && a != vert) {
            //if (a == 2) cout<<lv[a]<<endl<<endl<<endl;
           // cout<<a<<" "<<in[a]<<" "<<lv[a]<<endl;
            update(1,1,n,in[a],in[a],lv[a]);
        }
    } else
    update(1,1,n,in[a],in[a],lv[a]);
    for (int i = 0; i < v[a].size(); i++) {
        int to = v[a][i].f; int froma = v[a][i].s.f;  int fromto = v[a][i].s.s;
        if (to == p) continue;
        //if (to == 1 && vert) cout<<"asd"<<endl;
        dfs(to,a,froma,fromto);
    }
    out[a] = tin;
}
void dfs1(int a, int p) {
    ans[1] = min(ans[1], sum);
    if (ans[2] > sum - getans(1,1,n,1,n).mx) {
        vert = a;
        ans[2] = min(ans[2],sum - getans(1,1,n,1,n).mx);
    }
    for (int i = 0; i < v[a].size(); i++) {
        int to = v[a][i].f; int froma = v[a][i].s.f; int fromto = v[a][i].s.s;
        if (to == p) continue;
        sum -= froma; sum += fromto;
        update(1,1,n,in[to], out[to],-froma);
        update(1,1,n,1,in[to] - 1, fromto);
        update(1,1,n,out[to] + 1, n, fromto);
        dfs1(to,a);
        sum += froma; sum -= fromto;
        update(1,1,n,in[to], out[to], froma);
        update(1,1,n,1,in[to] - 1, -fromto);
        update(1,1,n,out[to] + 1, n, -fromto);
    }
}
main() {
	std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
  #define  endl '\n'
	emp = {0,0};
	cin>>n;
	for (int i = 1; i <= n - 1; i++) {
	    cin>>a[i]>>b[i]>>c[i]>>d[i];
	    v[a[i]].pb({b[i],{c[i],d[i]}});
	    v[b[i]].pb({a[i],{d[i],c[i]}});
	}
	ans[2] = ans[1] = 1e15;
	build(1,1,n);
	dfs(1,0,0,0);// cout<<sum<<endl;
	//cout<<getans(1,1,n,1,n)<<endl;
	dfs1(1,0);
	//cout<<ans[1]<<endl;
	//cout<<ans[2]<<endl;
	sum = 0;
	tin = 0;
	build(1,1,n);
	//cout<<vert<<endl;
	dfs(vert,0,0,0);
	
	for (int i = 2; i <= n; i++) {
	    int x = getans(1,1,n,1,n).mx;
	    int idx = ver[getans(1,1,n,1,n).idx];
	    //cout<<i<<"         "<<idx<<" "<<x<<endl;
	    sum -= x;
	    while (!fix[idx] && idx != vert) {
	        update(1,1,n,in[idx], out[idx], -up[idx]);
	        fix[idx] = 1;
	        idx = par[idx];
	    }
	    ans[i] = sum;
	   // cout<<ans[i]<<endl;
	}int q;cin>>q;
	while (q--) {
	    int x;
	    cin>>x;
	    cout<<ans[x]<<endl;
	}
}

/*
15
14 5 12 7
14 12 6 5
14 10 14 16
9 14 16 12
13 7 4 15
1 3 8 1
6 7 15 13
15 4 4 6
9 1 12 6
13 1 7 6
13 4 5 15
2 6 11 19
8 4 12 7
13 11 14 5
13
1
2
3
4
5
6
7
8
9
10
11
12
13
*/

Compilation message (stderr)

designated_cities.cpp: In function 'void dfs(long long int, long long int, long long int, long long int)':
designated_cities.cpp:93:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |     for (int i = 0; i < v[a].size(); i++) {
      |                     ~~^~~~~~~~~~~~~
designated_cities.cpp: In function 'void dfs1(long long int, long long int)':
designated_cities.cpp:107:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |     for (int i = 0; i < v[a].size(); i++) {
      |                     ~~^~~~~~~~~~~~~
designated_cities.cpp: At global scope:
designated_cities.cpp:121:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  121 | main() {
      | ^~~~

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