Submission #1113475

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1113475	2024-11-16T16:05:24 Z	Nonoze	Make them Meet (EGOI24_makethemmeet)	C++17	25.8644 / 100	108 ms	11496 KB

Main

#include <bits/stdc++.h>
using namespace std;

#define sz(x) (int)x.size()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define cmin(a, b) a=min(a, b)
#define cmax(a, b) a=max(a, b)
#define fi first
#define se second
#define pb push_back
#define mp make_pair

#define int long long

void solve();

signed main() {
	ios::sync_with_stdio(0); cin.tie(0);
	solve();
	return 0;
}

vector<vector<int>> vec;


void print() {
	cout << sz(vec) << endl;
	for (auto &a: vec) {
		for (auto &u: a) cout << u << ' ';
		cout << endl;
	}
	cout << endl;
}

void add(vector<int> &a) { vec.pb(a); }

int n, m;
vector<int> a;
vector<set<int>> adj;
vector<bool> visited;


void execute(int x) {
	visited[x]=1;
	for (auto u: adj[x]) if (!visited[u]) {
		auto temp=a; temp[x]=0, temp[u]=0;
		add(temp);
		execute(u);
		add(temp);
	}
}

void solve() {
	cin >> n >> m; a.clear(), a.resize(n, 0); iota(all(a), 1);
	adj.clear(), adj.resize(n);
	for (int i=0; i<m; i++) {
		int u, v; cin >> u >> v;
		adj[u].insert(v), adj[v].insert(u);
	}
	for (int i=0; i<n-1; i++) {
		int best=-1;
		for (int j=0; j<n; j++) if (sz(adj[j])!=0 && (best==-1 || sz(adj[best])>sz(adj[j]))) {
			best=j;
		}
		if (best==-1) break;
		visited.clear(), visited.resize(n, 0);
		execute(best);
		for (auto u: adj[best]) {
			adj[u].erase(best);
		}
		adj[best].clear();
	}
	print();
}

Subtask #1
3.694915254 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	1 ms	504 KB	Output is correct
3	Correct	1 ms	336 KB	Output is correct
4	Partially correct	77 ms	10868 KB	Partially correct
5	Partially correct	72 ms	11356 KB	Partially correct

Subtask #2
4.8033898302 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	1 ms	384 KB	Output is correct
3	Correct	1 ms	336 KB	Output is correct
4	Correct	1 ms	336 KB	Output is correct
5	Correct	2 ms	336 KB	Output is correct
6	Partially correct	5 ms	592 KB	Partially correct
7	Partially correct	7 ms	1276 KB	Partially correct
8	Partially correct	15 ms	1872 KB	Partially correct
9	Partially correct	74 ms	11396 KB	Partially correct

Subtask #3
4.0644067794 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	1 ms	336 KB	Output is correct
3	Correct	1 ms	336 KB	Output is correct
4	Partially correct	10 ms	1616 KB	Partially correct
5	Partially correct	62 ms	10884 KB	Partially correct
6	Partially correct	64 ms	11396 KB	Partially correct
7	Partially correct	19 ms	3232 KB	Partially correct

Subtask #4
13.3016949144 / 36.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	1 ms	504 KB	Output is correct
3	Correct	1 ms	336 KB	Output is correct
4	Partially correct	77 ms	10868 KB	Partially correct
5	Partially correct	72 ms	11356 KB	Partially correct
6	Correct	1 ms	336 KB	Output is correct
7	Correct	1 ms	336 KB	Output is correct
8	Correct	1 ms	336 KB	Output is correct
9	Partially correct	10 ms	1616 KB	Partially correct
10	Partially correct	62 ms	10884 KB	Partially correct
11	Partially correct	64 ms	11396 KB	Partially correct
12	Partially correct	19 ms	3232 KB	Partially correct
13	Correct	1 ms	336 KB	Output is correct
14	Correct	1 ms	336 KB	Output is correct
15	Correct	1 ms	336 KB	Output is correct
16	Partially correct	65 ms	10860 KB	Partially correct
17	Partially correct	65 ms	11372 KB	Partially correct
18	Correct	1 ms	336 KB	Output is correct
19	Correct	1 ms	336 KB	Output is correct
20	Partially correct	10 ms	1616 KB	Partially correct
21	Partially correct	108 ms	10948 KB	Partially correct
22	Partially correct	81 ms	11496 KB	Partially correct
23	Partially correct	19 ms	3152 KB	Partially correct
24	Correct	1 ms	336 KB	Output is correct
25	Correct	2 ms	336 KB	Output is correct
26	Correct	1 ms	336 KB	Output is correct
27	Partially correct	70 ms	11396 KB	Partially correct
28	Partially correct	70 ms	11396 KB	Partially correct
29	Partially correct	68 ms	11396 KB	Partially correct
30	Partially correct	67 ms	11396 KB	Partially correct
31	Partially correct	63 ms	11396 KB	Partially correct
32	Partially correct	72 ms	11396 KB	Partially correct
33	Partially correct	66 ms	11420 KB	Partially correct
34	Partially correct	65 ms	11396 KB	Partially correct
35	Partially correct	68 ms	11256 KB	Partially correct
36	Partially correct	79 ms	11396 KB	Partially correct
37	Partially correct	64 ms	11396 KB	Partially correct
38	Partially correct	68 ms	11396 KB	Partially correct
39	Partially correct	65 ms	11456 KB	Partially correct
40	Partially correct	89 ms	11396 KB	Partially correct
41	Partially correct	73 ms	11404 KB	Partially correct
42	Partially correct	64 ms	11396 KB	Partially correct
43	Partially correct	85 ms	11420 KB	Partially correct
44	Partially correct	66 ms	11396 KB	Partially correct
45	Partially correct	64 ms	11404 KB	Partially correct
46	Correct	1 ms	336 KB	Output is correct
47	Correct	1 ms	336 KB	Output is correct
48	Correct	1 ms	336 KB	Output is correct
49	Correct	1 ms	336 KB	Output is correct
50	Correct	1 ms	504 KB	Output is correct
51	Correct	1 ms	504 KB	Output is correct
52	Correct	1 ms	336 KB	Output is correct
53	Correct	1 ms	504 KB	Output is correct
54	Correct	1 ms	336 KB	Output is correct
55	Correct	1 ms	336 KB	Output is correct
56	Correct	1 ms	336 KB	Output is correct
57	Correct	1 ms	336 KB	Output is correct
58	Correct	1 ms	336 KB	Output is correct
59	Correct	1 ms	336 KB	Output is correct
60	Correct	1 ms	336 KB	Output is correct
61	Correct	1 ms	336 KB	Output is correct
62	Correct	1 ms	336 KB	Output is correct
63	Correct	1 ms	336 KB	Output is correct
64	Correct	1 ms	336 KB	Output is correct
65	Correct	1 ms	508 KB	Output is correct

Subtask #5
0.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	1 ms	504 KB	Output is correct
3	Correct	1 ms	336 KB	Output is correct
4	Partially correct	77 ms	10868 KB	Partially correct
5	Partially correct	72 ms	11356 KB	Partially correct
6	Correct	1 ms	336 KB	Output is correct
7	Correct	1 ms	384 KB	Output is correct
8	Correct	1 ms	336 KB	Output is correct
9	Correct	1 ms	336 KB	Output is correct
10	Correct	2 ms	336 KB	Output is correct
11	Partially correct	5 ms	592 KB	Partially correct
12	Partially correct	7 ms	1276 KB	Partially correct
13	Partially correct	15 ms	1872 KB	Partially correct
14	Partially correct	74 ms	11396 KB	Partially correct
15	Correct	1 ms	336 KB	Output is correct
16	Correct	1 ms	336 KB	Output is correct
17	Correct	1 ms	336 KB	Output is correct
18	Partially correct	10 ms	1616 KB	Partially correct
19	Partially correct	62 ms	10884 KB	Partially correct
20	Partially correct	64 ms	11396 KB	Partially correct
21	Partially correct	19 ms	3232 KB	Partially correct
22	Correct	1 ms	336 KB	Output is correct
23	Correct	1 ms	336 KB	Output is correct
24	Correct	1 ms	336 KB	Output is correct
25	Partially correct	65 ms	10860 KB	Partially correct
26	Partially correct	65 ms	11372 KB	Partially correct
27	Correct	1 ms	336 KB	Output is correct
28	Correct	1 ms	336 KB	Output is correct
29	Partially correct	10 ms	1616 KB	Partially correct
30	Partially correct	108 ms	10948 KB	Partially correct
31	Partially correct	81 ms	11496 KB	Partially correct
32	Partially correct	19 ms	3152 KB	Partially correct
33	Correct	1 ms	336 KB	Output is correct
34	Correct	2 ms	336 KB	Output is correct
35	Correct	1 ms	336 KB	Output is correct
36	Partially correct	70 ms	11396 KB	Partially correct
37	Partially correct	70 ms	11396 KB	Partially correct
38	Partially correct	68 ms	11396 KB	Partially correct
39	Partially correct	67 ms	11396 KB	Partially correct
40	Partially correct	63 ms	11396 KB	Partially correct
41	Partially correct	72 ms	11396 KB	Partially correct
42	Partially correct	66 ms	11420 KB	Partially correct
43	Partially correct	65 ms	11396 KB	Partially correct
44	Partially correct	68 ms	11256 KB	Partially correct
45	Partially correct	79 ms	11396 KB	Partially correct
46	Partially correct	64 ms	11396 KB	Partially correct
47	Partially correct	68 ms	11396 KB	Partially correct
48	Partially correct	65 ms	11456 KB	Partially correct
49	Partially correct	89 ms	11396 KB	Partially correct
50	Partially correct	73 ms	11404 KB	Partially correct
51	Partially correct	64 ms	11396 KB	Partially correct
52	Partially correct	85 ms	11420 KB	Partially correct
53	Partially correct	66 ms	11396 KB	Partially correct
54	Partially correct	64 ms	11404 KB	Partially correct
55	Correct	1 ms	336 KB	Output is correct
56	Correct	1 ms	336 KB	Output is correct
57	Correct	1 ms	336 KB	Output is correct
58	Correct	1 ms	336 KB	Output is correct
59	Correct	1 ms	504 KB	Output is correct
60	Correct	1 ms	504 KB	Output is correct
61	Correct	1 ms	336 KB	Output is correct
62	Correct	1 ms	504 KB	Output is correct
63	Correct	1 ms	336 KB	Output is correct
64	Correct	1 ms	336 KB	Output is correct
65	Correct	1 ms	336 KB	Output is correct
66	Correct	1 ms	336 KB	Output is correct
67	Correct	1 ms	336 KB	Output is correct
68	Correct	1 ms	336 KB	Output is correct
69	Correct	1 ms	336 KB	Output is correct
70	Correct	1 ms	336 KB	Output is correct
71	Correct	1 ms	336 KB	Output is correct
72	Correct	1 ms	336 KB	Output is correct
73	Correct	1 ms	336 KB	Output is correct
74	Correct	1 ms	508 KB	Output is correct
75	Correct	1 ms	336 KB	Output is correct
76	Correct	1 ms	508 KB	Output is correct
77	Correct	1 ms	504 KB	Output is correct
78	Partially correct	75 ms	11052 KB	Partially correct
79	Partially correct	63 ms	11444 KB	Partially correct
80	Correct	1 ms	336 KB	Output is correct
81	Correct	1 ms	336 KB	Output is correct
82	Correct	1 ms	336 KB	Output is correct
83	Correct	1 ms	336 KB	Output is correct
84	Partially correct	4 ms	592 KB	Partially correct
85	Partially correct	7 ms	1272 KB	Partially correct
86	Partially correct	11 ms	2040 KB	Partially correct
87	Partially correct	69 ms	11396 KB	Partially correct
88	Correct	1 ms	336 KB	Output is correct
89	Correct	1 ms	336 KB	Output is correct
90	Partially correct	10 ms	1628 KB	Partially correct
91	Partially correct	61 ms	10832 KB	Partially correct
92	Partially correct	63 ms	11396 KB	Partially correct
93	Partially correct	19 ms	3152 KB	Partially correct
94	Correct	1 ms	336 KB	Output is correct
95	Correct	1 ms	336 KB	Output is correct
96	Correct	1 ms	336 KB	Output is correct
97	Partially correct	72 ms	11280 KB	Partially correct
98	Partially correct	67 ms	11396 KB	Partially correct
99	Partially correct	73 ms	11396 KB	Partially correct
100	Partially correct	65 ms	11400 KB	Partially correct
101	Partially correct	78 ms	11396 KB	Partially correct
102	Partially correct	69 ms	11408 KB	Partially correct
103	Partially correct	67 ms	11396 KB	Partially correct
104	Partially correct	62 ms	11396 KB	Partially correct
105	Partially correct	71 ms	11396 KB	Partially correct
106	Partially correct	64 ms	11404 KB	Partially correct
107	Partially correct	65 ms	11396 KB	Partially correct
108	Partially correct	72 ms	11356 KB	Partially correct
109	Partially correct	82 ms	11396 KB	Partially correct
110	Partially correct	65 ms	11468 KB	Partially correct
111	Partially correct	65 ms	11396 KB	Partially correct
112	Partially correct	65 ms	11384 KB	Partially correct
113	Partially correct	71 ms	11396 KB	Partially correct
114	Partially correct	69 ms	11396 KB	Partially correct
115	Partially correct	68 ms	11396 KB	Partially correct
116	Correct	1 ms	500 KB	Output is correct
117	Correct	1 ms	336 KB	Output is correct
118	Correct	1 ms	336 KB	Output is correct
119	Correct	1 ms	336 KB	Output is correct
120	Correct	1 ms	336 KB	Output is correct
121	Correct	1 ms	592 KB	Output is correct
122	Correct	1 ms	336 KB	Output is correct
123	Correct	1 ms	336 KB	Output is correct
124	Correct	1 ms	336 KB	Output is correct
125	Correct	1 ms	336 KB	Output is correct
126	Correct	1 ms	504 KB	Output is correct
127	Correct	1 ms	336 KB	Output is correct
128	Correct	2 ms	336 KB	Output is correct
129	Correct	1 ms	336 KB	Output is correct
130	Correct	1 ms	336 KB	Output is correct
131	Correct	1 ms	376 KB	Output is correct
132	Correct	1 ms	508 KB	Output is correct
133	Correct	1 ms	336 KB	Output is correct
134	Correct	1 ms	336 KB	Output is correct
135	Correct	1 ms	336 KB	Output is correct
136	Correct	1 ms	336 KB	Output is correct
137	Correct	1 ms	336 KB	Output is correct
138	Correct	1 ms	336 KB	Output is correct
139	Correct	1 ms	336 KB	Output is correct
140	Partially correct	86 ms	11392 KB	Partially correct
141	Correct	1 ms	336 KB	Output is correct
142	Partially correct	71 ms	11412 KB	Partially correct
143	Partially correct	78 ms	11396 KB	Partially correct
144	Partially correct	72 ms	11396 KB	Partially correct
145	Partially correct	69 ms	11396 KB	Partially correct
146	Partially correct	67 ms	11296 KB	Partially correct
147	Partially correct	71 ms	11396 KB	Partially correct
148	Partially correct	91 ms	11380 KB	Partially correct
149	Partially correct	74 ms	11396 KB	Partially correct
150	Incorrect	34 ms	5972 KB	If people start at 0 and 2, then they can avoid each other
151	Halted	0 ms	0 KB	-

Submission #1113475

Compilation message

Subtask #1 3.694915254 / 10.0

Subtask #2 4.8033898302 / 13.0

Subtask #3 4.0644067794 / 11.0

Subtask #4 13.3016949144 / 36.0

Subtask #5 0.0 / 30.0

Subtask #1
3.694915254 / 10.0

Subtask #2
4.8033898302 / 13.0

Subtask #3
4.0644067794 / 11.0

Subtask #4
13.3016949144 / 36.0

Subtask #5
0.0 / 30.0