Submission #125295

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
125295	2019-07-05T04:55:34 Z	이온조(#3059)	Arranging Tickets (JOI17_arranging_tickets)	C++14	10 / 100	148 ms	504 KB

arranging_tickets

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

// struct PST {
// 	vector<int> root;
// 	vector<long long> T;


// };

int A[200009], B[200009], S[200009];

int main() {
	int N, M; scanf("%d%d",&N,&M);
	for(int i=0; i<M; i++) {
		int a, b, c; scanf("%d%d%d",&a,&b,&c);
		if(a > b) swap(a, b);
		A[i] = a; B[i] = b;
	}
	int ans = 1e9;
	for(int i=0; i<(1<<M); i++) {
		for(int j=1; j<=N; j++) S[j] = 0;
		for(int j=0; j<M; j++) {
			if(i & (1 << j)) {
				++S[A[j]];
				--S[B[j]];
			}
			else {
				++S[1]; --S[A[j]];
				++S[B[j]];
			}
		}
		int mx = 0;
		for(int j=1, s=0; j<=N; j++) {
			s += S[j];
			mx = max(mx, s);
		}
		ans = min(ans, mx);
	}
	printf("%d", ans);
	return 0;
}

Compilation message

arranging_tickets.cpp: In function 'int main()':
arranging_tickets.cpp:15:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int N, M; scanf("%d%d",&N,&M);
            ~~~~~^~~~~~~~~~~~~~
arranging_tickets.cpp:17:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int a, b, c; scanf("%d%d%d",&a,&b,&c);
                ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	136 ms	408 KB	Output is correct
2	Correct	135 ms	376 KB	Output is correct
3	Correct	136 ms	384 KB	Output is correct
4	Correct	148 ms	376 KB	Output is correct
5	Correct	139 ms	376 KB	Output is correct
6	Correct	135 ms	388 KB	Output is correct
7	Correct	135 ms	376 KB	Output is correct
8	Correct	137 ms	504 KB	Output is correct
9	Correct	136 ms	376 KB	Output is correct
10	Correct	136 ms	376 KB	Output is correct
11	Correct	136 ms	376 KB	Output is correct
12	Correct	137 ms	376 KB	Output is correct
13	Correct	135 ms	376 KB	Output is correct
14	Correct	135 ms	380 KB	Output is correct
15	Correct	138 ms	380 KB	Output is correct

Subtask #2

0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	136 ms	408 KB	Output is correct
2	Correct	135 ms	376 KB	Output is correct
3	Correct	136 ms	384 KB	Output is correct
4	Correct	148 ms	376 KB	Output is correct
5	Correct	139 ms	376 KB	Output is correct
6	Correct	135 ms	388 KB	Output is correct
7	Correct	135 ms	376 KB	Output is correct
8	Correct	137 ms	504 KB	Output is correct
9	Correct	136 ms	376 KB	Output is correct
10	Correct	136 ms	376 KB	Output is correct
11	Correct	136 ms	376 KB	Output is correct
12	Correct	137 ms	376 KB	Output is correct
13	Correct	135 ms	376 KB	Output is correct
14	Correct	135 ms	380 KB	Output is correct
15	Correct	138 ms	380 KB	Output is correct
16	Incorrect	8 ms	376 KB	Output isn't correct
17	Halted	0 ms	0 KB	-

Subtask #3

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	136 ms	408 KB	Output is correct
2	Correct	135 ms	376 KB	Output is correct
3	Correct	136 ms	384 KB	Output is correct
4	Correct	148 ms	376 KB	Output is correct
5	Correct	139 ms	376 KB	Output is correct
6	Correct	135 ms	388 KB	Output is correct
7	Correct	135 ms	376 KB	Output is correct
8	Correct	137 ms	504 KB	Output is correct
9	Correct	136 ms	376 KB	Output is correct
10	Correct	136 ms	376 KB	Output is correct
11	Correct	136 ms	376 KB	Output is correct
12	Correct	137 ms	376 KB	Output is correct
13	Correct	135 ms	376 KB	Output is correct
14	Correct	135 ms	380 KB	Output is correct
15	Correct	138 ms	380 KB	Output is correct
16	Incorrect	8 ms	376 KB	Output isn't correct
17	Halted	0 ms	0 KB	-

Subtask #4

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	136 ms	408 KB	Output is correct
2	Correct	135 ms	376 KB	Output is correct
3	Correct	136 ms	384 KB	Output is correct
4	Correct	148 ms	376 KB	Output is correct
5	Correct	139 ms	376 KB	Output is correct
6	Correct	135 ms	388 KB	Output is correct
7	Correct	135 ms	376 KB	Output is correct
8	Correct	137 ms	504 KB	Output is correct
9	Correct	136 ms	376 KB	Output is correct
10	Correct	136 ms	376 KB	Output is correct
11	Correct	136 ms	376 KB	Output is correct
12	Correct	137 ms	376 KB	Output is correct
13	Correct	135 ms	376 KB	Output is correct
14	Correct	135 ms	380 KB	Output is correct
15	Correct	138 ms	380 KB	Output is correct
16	Incorrect	8 ms	376 KB	Output isn't correct
17	Halted	0 ms	0 KB	-

Subtask #5

0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	136 ms	408 KB	Output is correct
2	Correct	135 ms	376 KB	Output is correct
3	Correct	136 ms	384 KB	Output is correct
4	Correct	148 ms	376 KB	Output is correct
5	Correct	139 ms	376 KB	Output is correct
6	Correct	135 ms	388 KB	Output is correct
7	Correct	135 ms	376 KB	Output is correct
8	Correct	137 ms	504 KB	Output is correct
9	Correct	136 ms	376 KB	Output is correct
10	Correct	136 ms	376 KB	Output is correct
11	Correct	136 ms	376 KB	Output is correct
12	Correct	137 ms	376 KB	Output is correct
13	Correct	135 ms	376 KB	Output is correct
14	Correct	135 ms	380 KB	Output is correct
15	Correct	138 ms	380 KB	Output is correct
16	Incorrect	8 ms	376 KB	Output isn't correct
17	Halted	0 ms	0 KB	-