Submission #260457

#	Time	Username	Problem	Language	Result	Execution time	Memory
260457		patrikpavic2	Designated Cities (JOI19_designated_cities)	C++17	22 / 100	366 ms	33148 KiB

designated_cities

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <vector>

#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 < pip > v[N], v2[N];

ll C[N], uk, sol1, sol2, solt, sol[N];
int n, bio[20];

void start(int x, int lst){
	for(pip nxt : v[x]){
		if(nxt.X == lst) continue;
		C[1] += nxt.Y.X; start(nxt.X, x);
	}
}

void dfs(int x, int lst){
	for(pip nxt : v[x]){
		if(nxt.X == lst) continue;
		C[nxt.X] = C[x] - nxt.Y.X + nxt.Y.Y;
		dfs(nxt.X, x);
	}
	sol1 = max(sol1, C[x]);
}

ll dfs2(int x, int lst){
	ll dos = C[x];
	for(pip nxt : v[x]){
		if(nxt.X == lst) continue;
		ll sad = dfs2(nxt.X, x) + nxt.Y.X + nxt.Y.Y;
		sol2 = max(sol2, dos + sad);
		dos = max(dos, sad);
	}	
	return dos;
}

void dfs3(int x, int lst){
	for(pip &nxt : v2[x]){
		if(nxt.X == lst) continue;
		solt += nxt.Y.X; nxt.Y.X = 0;
		dfs3(nxt.X, x);
	}
}

void odradi(int msk){
	for(int i = 1;i <= n;i++)
		v2[i] = v[i];
	solt = 0; int kol = 0;
	for(int i = 1;i <= n;i++){
		if(msk & (1 << (i - 1)))
			dfs3(i, i), kol++;
	}
	sol[kol] = max(sol[kol], solt);	
}

int main(){
	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, b}}); v[y].PB({x, {b, a}});
		uk += a + b;
	}
	int q; scanf("%d", &q);
	if(n <= 16){
		for(int i = 0;i < (1 << n);i++)
			odradi(i);
		for(;q--;){
			int x; scanf("%d", &x);
			printf("%lld\n", uk - sol[x]);
		}
		return 0;
	}
	if(q > 1) return 0;
	int kol; scanf("%d", &kol);
	if(kol > 2) return 0;
	start(1, 1); dfs(1, 1);
	if(kol == 1){
		printf("%lld\n", uk - sol1);
	}
	else{
		dfs2(1, 1);
		printf("%lld\n", uk - sol2 / 2);
	}
}

Compilation message (stderr)

designated_cities.cpp: In function 'int main()':
designated_cities.cpp:70:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
designated_cities.cpp:72: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:76: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:81:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    int x; scanf("%d", &x);
           ~~~~~^~~~~~~~~~
designated_cities.cpp:87:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int kol; scanf("%d", &kol);
           ~~~~~^~~~~~~~~~~~

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