oj.uz

Submission #153293

# Submission time Handle Problem Language Result Execution time Memory
153293 2019-09-13T11:23:38 Z username Designated Cities (JOI19_designated_cities) C++14
16 / 100
 502 ms 44924 KB 
#include<bits/stdc++.h>
#define int int64_t
using namespace std;
typedef pair<int,int> pii;
#define REP(i,j,k) for(int i=(j);i<(k);++i)
#define MAX(x,y) (x=max(x,(y)))
#define pb push_back
#define f first
#define s second
#define endl '\n'
#define IOS cin.tie(0),cout.tie(0),ios_base::sync_with_stdio(false)

struct tup{int f,s,t;};
const int maxn=2e5+9;
int n,q,s=0,k=0,x=0,res[maxn];
vector<tup>g[maxn];
vector<int>ch;

pii far(int u,int f){
	pii ret={0,u};
	REP(i,0,g[u].size()){
		tup&e=g[u][i];
		if(e.f==f)continue;
		pii tt=far(e.f,u);
		MAX(ret,pii(tt.f+e.s,tt.s));
	}
	return ret;
}

int tdc(int u,int f){
	int mx=0;
	REP(i,0,g[u].size()){
		tup&e=g[u][i];
		if(e.f==f){
			k+=e.s;
			continue;
		}
		int t=tdc(e.f,u)+e.s;
		if(t>mx){
			if(mx>0)ch.pb(mx);
			mx=t;
		}
	}
	return mx;
}

void dfs(int u,int f){
	REP(i,0,g[u].size()){
		tup&e=g[u][i];
		if(e.f==f){
			x+=e.s;
			continue;
		}
		dfs(e.f,u);
	}
}

void calc(int u,int f){
	MAX(res[1],x);
	REP(i,0,g[u].size()){
		tup&e=g[u][i];
		if(e.f==f)continue;
		x+=e.s-e.t;
		calc(e.f,u);
		x-=e.s-e.t;
	}
}

main(){
	IOS;
	cin>>n;
	REP(i,1,n){
		int a,b,c,d;cin>>a>>b>>c>>d,--a,--b;
		g[a].pb(tup{b,c,d});
		g[b].pb(tup{a,d,c});
		s+=c+d;
	}
	ch.pb(tdc(far(far(0,-1).s,-1).s,-1));
	sort(ch.begin(),ch.end(),[](int a,int b){return a>b;});
	res[1]=k;
	REP(i,2,n+1)res[i]=res[i-1]+(i-2<ch.size()?ch[i-2]:0);
	dfs(0,-1);
	calc(0,-1);
	cin>>q;
	REP(i,0,q){
		int e;cin>>e;
		cout<<s-res[e]<<endl;
	}
}

Compilation message

designated_cities.cpp: In function 'pii far(int64_t, int64_t)':
designated_cities.cpp:5:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(i,j,k) for(int i=(j);i<(k);++i)
                                   ^
designated_cities.cpp:21:2: note: in expansion of macro 'REP'
  REP(i,0,g[u].size()){
  ^~~
designated_cities.cpp: In function 'int64_t tdc(int64_t, int64_t)':
designated_cities.cpp:5:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(i,j,k) for(int i=(j);i<(k);++i)
                                   ^
designated_cities.cpp:32:2: note: in expansion of macro 'REP'
  REP(i,0,g[u].size()){
  ^~~
designated_cities.cpp: In function 'void dfs(int64_t, int64_t)':
designated_cities.cpp:5:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(i,j,k) for(int i=(j);i<(k);++i)
                                   ^
designated_cities.cpp:48:2: note: in expansion of macro 'REP'
  REP(i,0,g[u].size()){
  ^~~
designated_cities.cpp: In function 'void calc(int64_t, int64_t)':
designated_cities.cpp:5:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(i,j,k) for(int i=(j);i<(k);++i)
                                   ^
designated_cities.cpp:60:2: note: in expansion of macro 'REP'
  REP(i,0,g[u].size()){
  ^~~
designated_cities.cpp: At global scope:
designated_cities.cpp:69:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
designated_cities.cpp: In function 'int main()':
designated_cities.cpp:81:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  REP(i,2,n+1)res[i]=res[i-1]+(i-2<ch.size()?ch[i-2]:0);
                               ~~~^~~~~~~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Incorrect 7 ms 4984 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 6 ms 4984 KB Output is correct
2 Correct 400 ms 26428 KB Output is correct
3 Correct 496 ms 44924 KB Output is correct
4 Correct 365 ms 24736 KB Output is correct
5 Correct 353 ms 26328 KB Output is correct
6 Correct 398 ms 29008 KB Output is correct
7 Correct 354 ms 25252 KB Output is correct
8 Correct 479 ms 44296 KB Output is correct
9 Correct 203 ms 24092 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 384 ms 26384 KB Output is correct
3 Correct 496 ms 44920 KB Output is correct
4 Correct 364 ms 24824 KB Output is correct
5 Correct 345 ms 26408 KB Output is correct
6 Correct 402 ms 29760 KB Output is correct
7 Correct 211 ms 24088 KB Output is correct
8 Correct 502 ms 38644 KB Output is correct
9 Correct 204 ms 23704 KB Output is correct

Subtask #4
0 / 17.0

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

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 400 ms 26428 KB Output is correct
3 Correct 496 ms 44924 KB Output is correct
4 Correct 365 ms 24736 KB Output is correct
5 Correct 353 ms 26328 KB Output is correct
6 Correct 398 ms 29008 KB Output is correct
7 Correct 354 ms 25252 KB Output is correct
8 Correct 479 ms 44296 KB Output is correct
9 Correct 203 ms 24092 KB Output is correct
10 Correct 6 ms 4984 KB Output is correct
11 Correct 384 ms 26384 KB Output is correct
12 Correct 496 ms 44920 KB Output is correct
13 Correct 364 ms 24824 KB Output is correct
14 Correct 345 ms 26408 KB Output is correct
15 Correct 402 ms 29760 KB Output is correct
16 Correct 211 ms 24088 KB Output is correct
17 Correct 502 ms 38644 KB Output is correct
18 Correct 204 ms 23704 KB Output is correct
19 Correct 6 ms 5112 KB Output is correct
20 Incorrect 420 ms 26460 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

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