oj.uz

Submission #261397

# Submission time Handle Problem Language Result Execution time Memory
261397 2020-08-11T17:10:32 Z patrikpavic2 Designated Cities (JOI19_designated_cities) C++17
7 / 100
 698 ms 39440 KB 
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <set>

#define X first
#define Y second
#define PB push_back

using namespace std;

typedef long long ll;
typedef pair < int, int > pii;
typedef pair < int, pii > pip;

const int N = 2e5 + 500;

vector < pii > v[N];
vector < pip > v2[N];

set < pii > S;

int n, deg[N], bio[N];
ll cur, bst[N];
ll C[N], uk;
 
void start(int x, int lst){
	for(pip nxt : v2[x]){
		if(nxt.X == lst) continue;
		C[1] += nxt.Y.X; start(nxt.X, x);
	}
}
 
void dfs(int x, int lst){
	for(pip nxt : v2[x]){
		if(nxt.X == lst) continue;
		C[nxt.X] = C[x] - nxt.Y.X + nxt.Y.Y;
		dfs(nxt.X, x);
	}
	bst[1] = max(bst[1], C[x]);
}

inline int pronadi(int x){
	for(pii nxt : v[x])
		if(deg[nxt.X])
			return nxt.Y;
	return 0;
}


int main(){
	for(int i = 0;i < N;i++)
		bst[i] = 1e18;
	scanf("%d", &n);
	for(int i = 1;i < n;i++){
		int x, y, a, b; scanf("%d%d%d%d", &x, &y, &b, &a);
		v[x].PB({y, a}); v[y].PB({x, b});
		v2[x].PB({y, {a, b}}); v2[y].PB({x, {b, a}});
		uk += a + b;
		deg[x]++; deg[y]++;
	}
	for(int i = 1;i <= n;i++){
		if(deg[i] == 1)
			S.insert({v[i][0].Y, i});
	}
	bst[(int)S.size()] = cur;
	int lisce = (int)S.size();
	for(;S.size() > 2;){
		int brs = S.begin() -> Y; 
		cur += S.begin() -> X; deg[brs] = 0;
		S.erase(S.begin());
		for(pii nxt : v[brs]){
			if(deg[nxt.X] > 0){
				deg[nxt.X]--;
				if(deg[nxt.X] == 1)
					S.insert({pronadi(nxt.X), nxt.X});
				break;
			}
		}
		bst[(int)S.size()] = min(bst[(int)S.size()], cur);
	}
	bst[1] = 0;
	start(1, 1); dfs(1, 1);
	bst[1] = uk - bst[1];
	int q; scanf("%d", &q);
	for(;q--;){
		int x; scanf("%d", &x);
		x = min(x, lisce);
		printf("%lld\n", bst[x]);
	}
	
}

Compilation message

designated_cities.cpp: In function 'int main()':
designated_cities.cpp:55:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
designated_cities.cpp:57:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x, y, a, b; scanf("%d%d%d%d", &x, &y, &b, &a);
                   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
designated_cities.cpp:86:14: 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:88:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x; scanf("%d", &x);
          ~~~~~^~~~~~~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 11264 KB Output is correct
2 Incorrect 8 ms 11264 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 11264 KB Output is correct
2 Correct 614 ms 33120 KB Output is correct
3 Correct 520 ms 33816 KB Output is correct
4 Correct 632 ms 33016 KB Output is correct
5 Correct 683 ms 33448 KB Output is correct
6 Correct 684 ms 34044 KB Output is correct
7 Correct 608 ms 35064 KB Output is correct
8 Correct 552 ms 34940 KB Output is correct
9 Correct 578 ms 39440 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 11264 KB Output is correct
2 Incorrect 698 ms 33000 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 11264 KB Output is correct
2 Incorrect 8 ms 11264 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 11264 KB Output is correct
2 Correct 614 ms 33120 KB Output is correct
3 Correct 520 ms 33816 KB Output is correct
4 Correct 632 ms 33016 KB Output is correct
5 Correct 683 ms 33448 KB Output is correct
6 Correct 684 ms 34044 KB Output is correct
7 Correct 608 ms 35064 KB Output is correct
8 Correct 552 ms 34940 KB Output is correct
9 Correct 578 ms 39440 KB Output is correct
10 Correct 10 ms 11264 KB Output is correct
11 Incorrect 698 ms 33000 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

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