CSES - Datatähti 2022 alku - Results
Submission details
Task:Tietoverkko (Network)
Sender:victor05
Submission time:2021-10-17 14:10:58
Language:C++11
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
Test results
testverdicttimegroup
#10.07 s1, 2, 3details
#2--2, 3details
#3--3details

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:9:27: warning: unused variable 'k' [-Wunused-variable]
  uint64_t n, *c, i, j, l, k, lowest, dest, r;
                           ^
input/code.cpp: In function 'bool testBranch(uint64_t*, uint64_t, uint64_t, uint64_t, uint64_t, uint64_t*)':
input/code.cpp:67:20: warning: unused variable 'OL' [-Wunused-variable]
  uint64_t i, l, L, OL;
                    ^~
input/code.cpp: In function 'int main()':
input/code.cpp:11:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%ld", &n);
  ~~~~~^~~~~~~~~~~
input/code.cpp:16:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%ld %ld %ld", (c + (i * 3)), (c + (i * 3) + 1), (c + (i * 3) + 2));
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Code

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <stdbool.h>

bool testBranch(uint64_t *network, uint64_t n, uint64_t location, uint64_t dest, uint64_t target, uint64_t *lowest);

int main(void) {
	uint64_t n, *c, i, j, l, k, lowest, dest, r;

	scanf("%ld", &n);

	c = (uint64_t *)calloc(sizeof(uint64_t), (n-1) * 3);

	for(i = 0; i < n - 1; i++) {
		scanf("%ld %ld %ld", (c + (i * 3)), (c + (i * 3) + 1), (c + (i * 3) + 2));
	}

	r = 0;

	for(i = 1; i < n; i++) {
		for(j = i+1; j < n+1; j++) {
			for(l = 0; l < n-1; l++) {
				if(*(c + (l * 3)) == i) {

					if(*(c + (l * 3) + 1) == j) {
						r += *(c + (l * 3) + 2);
						break;
					}

					lowest = *(c + (l * 3) + 2);
					dest = *(c + (l * 3) + 1);

					if(testBranch(c, n, l, dest, j, &lowest)) {
						r += lowest;
						break;
					}

				}

				else if(*(c + (l * 3) + 1) == i) {

					if(*(c + (l * 3)) == j) {
						r += *(c + (l * 3) + 2);
						break;
					}

					lowest = *(c + (l * 3) + 2);
					dest = *(c + (l * 3));

					if(testBranch(c, n, l, dest, j, &lowest)) {
						r += lowest;
						break;
					}
				}
			}
		}
	}

	printf("%ld\n", r);


	return 0;
}

bool testBranch(uint64_t *network, uint64_t n, uint64_t location, uint64_t dest, uint64_t target, uint64_t *lowest) {
	uint64_t i, l, L, OL;
	
	L = *lowest;

	if(location != 0) {
		i = location-1;
		while(true) {
			if(*lowest > *(network + (i*3) + 2)) {
				L = *lowest;
				*lowest = *(network + (i*3) + 2);
			}

			if((*(network + (i*3)) == dest && *(network + (i*3) + 1) == target)) {
				return true;
			}

			else if((*(network + (i*3)+1) == dest && *(network + (i*3)) == target)) {
				return true;
			}

			else if(*(network + (i*3)) == dest) {
				l = *lowest;
				if(testBranch(network, n, i, *(network + (i*3)+1), target, &l)) {
					*lowest = l;
					return true;
				}

				*lowest = L;

			}

			else if(*(network + (i*3)+1) == dest) {
				l = *lowest;
				if(testBranch(network, n, i, *(network + (i*3)), target, &l)) {
					*lowest = l;
					return true;
				}

				*lowest = L;

			}

			if(i == 0)
				break;

			i--;
		}
	}

	*lowest = L;

	for(i = location+1; i < n-1; i++) {
		if(*lowest > *(network + (i*3) + 2)) {
			L = *lowest;
			*lowest = *(network + (i*3) + 2);
		}

		if((*(network + (i*3)) == dest && *(network + (i*3) + 1) == target)) {
			return true;
		}

		else if((*(network + (i*3)+1) == dest && *(network + (i*3)) == target)) {
			return true;
		}

		else if(*(network + (i*3)) == dest) {
			l = *lowest;
			if(testBranch(network, n, i, *(network + (i*3)+1), target, &l)) {
				*lowest = l;
				return true;
			}

			*lowest = L;

		}

		else if(*(network + (i*3)+1) == dest) {
			l = *lowest;
			if(testBranch(network, n, i, *(network + (i*3)), target, &l)) {
				*lowest = l;
				return true;
			}

			*lowest = L;

		}

		else {
			*lowest = L;
		}
	}

	return false;
}

Test details

Test 1

Group: 1, 2, 3

Verdict:

input
100
1 2 74
1 3 100
2 4 50
3 5 40
...

correct output
88687

user output
46661

Test 2

Group: 2, 3

Verdict:

input
5000
1 2 613084013
1 3 832364259
2 4 411999902
3 5 989696303
...

correct output
1103702320243776

user output
(empty)

Test 3

Group: 3

Verdict:

input
200000
1 2 613084013
1 3 832364259
2 4 411999902
3 5 989696303
...

correct output
1080549209850010931

user output
(empty)