oj.uz

Submission #204167

# Submission time Handle Problem Language Result Execution time Memory
204167 2020-02-24T19:29:43 Z cheetose Designated Cities (JOI19_designated_cities) C++17
16 / 100
 428 ms 39800 KB 
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define X first
#define Y second
#define y0 y12
#define y1 y22
#define INF 987654321
#define PI 3.141592653589793238462643383279502884
#define fup(i,a,b,c) for(int (i)=(a);(i)<=(b);(i)+=(c))
#define fdn(i,a,b,c) for(int (i)=(a);(i)>=(b);(i)-=(c))
#define MEM0(a) memset((a),0,sizeof(a));
#define MEM_1(a) memset((a),-1,sizeof(a));
#define ALL(a) a.begin(),a.end()
#define SYNC ios_base::sync_with_stdio(false);cin.tie(0)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef double db;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int, int> Pi;
typedef pair<ll, ll> Pll;
typedef pair<ld, ld> Pd;
typedef vector<int> Vi;
typedef vector<ll> Vll;
typedef vector<ld> Vd;
typedef vector<Pi> VPi;
typedef vector<Pll> VPll;
typedef vector<Pd> VPd;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef tuple<ll, ll, ll> LLL;
typedef vector<iii> Viii;
typedef vector<LLL> VLLL;
typedef complex<double> base;
const int MOD = 1000000007;
ll POW(ll a, ll b, ll MMM = MOD) { ll ret = 1; for (; b; b >>= 1, a = (a*a) % MMM)if (b & 1)ret = (ret*a) % MMM; return ret; }
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
ll lcm(ll a, ll b) { if (a == 0 || b == 0)return a + b; return a*(b / gcd(a, b)); }
int dx[] = { 0,1,0,-1,1,1,-1,-1 }, dy[] = { 1,0,-1,0,1,-1,1,-1 };
int ddx[] = { -1,-2,1,-2,2,-1,2,1 }, ddy[] = { -2,-1,-2,1,-1,2,1,2 };

struct A{
	int y;
	ll c,d;
};
vector<A> v[200001];
ll sum,ans[200001];
ll Q1[200001],Q2[200001],q1;
ll dfs1(int N,int p=-1)
{
	ll res=0;
	for(auto &P:v[N])
	{
		if(P.y==p)continue;
		res+=P.d+dfs1(P.y,N);
	}
	return res;
}
void dfs2(int N,ll now,int p=-1)
{
	q1=max(q1,now);
	Q1[N]=now;
	for(auto &P:v[N])
	{
		if(P.y==p)continue;
		dfs2(P.y,now+P.c-P.d,N);
	}
}
ll dfs3(int N,int p=-1)
{
	Vll V;
	for(auto &P:v[N])
	{
		if(P.y==p)continue;
		V.pb(P.c+dfs3(P.y,N));
	}
	if(V.empty())return 0;
	sort(V.rbegin(),V.rend());
	if(V.size()>1)Q2[N]=Q1[N]+V[0]+V[1];
	return V[0];
}
int main() {
	int n,R;
	scanf("%d",&n);
	if(n==2)
	{
		int a,b,c,d,q;
		scanf("%d%d%d%d%d",&a,&b,&c,&d,&q);
		while(q--)
		{
			int x;
			scanf("%d",&x);
			if(x==1)printf("%d\n",min(c,d));
			else puts("0");
		}
		return 0;
	}
	fup(i,1,n-1,1)
	{
		int x,y;
		ll c,d;
		scanf("%d%d%lld%lld",&x,&y,&c,&d);
		sum+=c+d;
		v[x].pb({y,c,d});
		v[y].pb({x,d,c});
	}
	fup(i,1,n,1)if(v[i].size()>1)R=i;
	ll now=dfs1(R);
	dfs2(R,now);
	int q;
	scanf("%d",&q);
	ans[1]=sum-q1;
	dfs3(R);
	int w=-1;
	ll mx=-1;
	fup(i,1,n,1)
		if(Q2[i]>mx)w=i,mx=Q2[i];
	ans[2]=sum-mx;
	while(q--)
	{
		int x;
		scanf("%d",&x);
		printf("%lld\n",ans[x]);
	}
}

Compilation message

designated_cities.cpp: In function 'int main()':
designated_cities.cpp:116:6: warning: variable 'w' set but not used [-Wunused-but-set-variable]
  int w=-1;
      ^
designated_cities.cpp:86:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
designated_cities.cpp:90:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d%d%d",&a,&b,&c,&d,&q);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
designated_cities.cpp:94:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&x);
    ~~~~~^~~~~~~~~
designated_cities.cpp:104:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%lld%lld",&x,&y,&c,&d);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
designated_cities.cpp:113:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&q);
  ~~~~~^~~~~~~~~
designated_cities.cpp:124:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&x);
   ~~~~~^~~~~~~~~
designated_cities.cpp:110:15: warning: 'R' may be used uninitialized in this function [-Wmaybe-uninitialized]
  ll now=dfs1(R);
               ^

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4984 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 8 ms 4984 KB Output is correct
2 Correct 369 ms 23544 KB Output is correct
3 Correct 428 ms 34168 KB Output is correct
4 Correct 345 ms 22520 KB Output is correct
5 Correct 361 ms 24168 KB Output is correct
6 Correct 378 ms 25980 KB Output is correct
7 Correct 296 ms 24352 KB Output is correct
8 Correct 426 ms 38392 KB Output is correct
9 Correct 221 ms 23576 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4984 KB Output is correct
2 Correct 372 ms 23404 KB Output is correct
3 Correct 421 ms 37600 KB Output is correct
4 Correct 351 ms 26360 KB Output is correct
5 Correct 352 ms 28200 KB Output is correct
6 Correct 380 ms 30136 KB Output is correct
7 Correct 238 ms 28828 KB Output is correct
8 Correct 424 ms 39800 KB Output is correct
9 Correct 220 ms 27288 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4984 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 8 ms 4984 KB Output is correct
2 Correct 369 ms 23544 KB Output is correct
3 Correct 428 ms 34168 KB Output is correct
4 Correct 345 ms 22520 KB Output is correct
5 Correct 361 ms 24168 KB Output is correct
6 Correct 378 ms 25980 KB Output is correct
7 Correct 296 ms 24352 KB Output is correct
8 Correct 426 ms 38392 KB Output is correct
9 Correct 221 ms 23576 KB Output is correct
10 Correct 8 ms 4984 KB Output is correct
11 Correct 372 ms 23404 KB Output is correct
12 Correct 421 ms 37600 KB Output is correct
13 Correct 351 ms 26360 KB Output is correct
14 Correct 352 ms 28200 KB Output is correct
15 Correct 380 ms 30136 KB Output is correct
16 Correct 238 ms 28828 KB Output is correct
17 Correct 424 ms 39800 KB Output is correct
18 Correct 220 ms 27288 KB Output is correct
19 Correct 9 ms 4984 KB Output is correct
20 Incorrect 381 ms 27396 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

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