#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
//Query(int a, int b, int c)
//Bridge(int first, int second)
//edges from 0 to n-1
typedef long long ll;
ll acns = 100000000;
ll bcns = 10000;
unordered_map<ll,int> querymap;
int n;
int squery(int a, int b, int c){
//cout<<"query "<<a<<" "<<b<<" "<<c<<endl;
if (a>b){
swap(a,b);
}
if (b>c){
swap(b,c);
}
if (a>b){
swap(a,b);
}
if (b>c){
swap(b,c);
}
ll q = a*acns+b*bcns+c;
auto f = querymap.find(q);
if (f==querymap.end()){
return querymap[q]=Query(a,b,c);
} else {
return (*f).second;
}
}
int sortstart, sortend;
bool sfunction(int a, int b){
return (squery(sortstart,a,b)==a);
}
void solverecursive(int start, vector<int> &arrayUsing){
int row[2000];
/*cout<<"===="<<endl;
for (int i : arrayUsing){
cout<<i<<" ";
}cout<<endl;*/
int end = arrayUsing[0];
int ptr = 0;
//deque<int> row;
//row.push_back(start);
//row.push_back(end);
vector<vector<int> > children(n);
for (int i = 1; i<arrayUsing.size(); i++){
int node = squery(start,end,arrayUsing[i]);
if (node==start){
row[ptr]=start;
ptr++;
//row.push_front(arrayUsing[i]);
start=arrayUsing[i];
} else if (node==end){
row[ptr]=end;
ptr++;
//row.push_back(arrayUsing[i]);
end=arrayUsing[i];
} else if (node==arrayUsing[i]){
row[ptr]=node;
ptr++;
//row[row.size()-1]=node;
//row.push_back(end);
} else {
children[node].push_back(arrayUsing[i]);
}
}
//sort
if (ptr>1){
sortstart=start;
sortend=end;
sort(row,row+ptr,sfunction);
}
/*cout<<start<<" ";
for (int i = 0; i<ptr; i++){
cout<<row[i]<<" ";
}cout<<end<<" "<<endl;*/
//cout<<"bridge "<<min(start,row[0])<<" "<<max(start,row[0])<<endl;
Bridge(min(start,row[0]),max(start,row[0]));
row[ptr]=end;
for (int i = 0; i<ptr; i++){
//cout<<"bridge "<<min(row[i],row[i+1])<<" "<<max(row[i],row[i+1])<<endl;
Bridge(min(row[i],row[i+1]),max(row[i],row[i+1]));
if (children[row[i]].size()==0){
continue;
} else if (children[row[i]].size()==1){
//cout<<"bridge "<<min(row[i],children[row[i]][0])<<" "<<max(row[i],children[row[i]][0])<<endl;
Bridge(min(row[i],children[row[i]][0]),max(row[i],children[row[i]][0]));
} else {
solverecursive(row[i],children[row[i]]);
}
}//add case where i=row.size()-1
}
void Solve(int N) {
n = N;
vector<int> arrayUsing;
arrayUsing.resize(n-1,0);
for (int i = 1; i<n; i++){
arrayUsing[i-1]=i;
}
solverecursive(0,arrayUsing);
}
Compilation message
meetings.cpp: In function 'void solverecursive(int, std::vector<int>&)':
meetings.cpp:52:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 1; i<arrayUsing.size(); i++){
~^~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
248 KB |
Output is correct |
2 |
Correct |
2 ms |
248 KB |
Output is correct |
3 |
Correct |
2 ms |
248 KB |
Output is correct |
4 |
Correct |
2 ms |
248 KB |
Output is correct |
5 |
Correct |
2 ms |
248 KB |
Output is correct |
6 |
Correct |
2 ms |
380 KB |
Output is correct |
7 |
Correct |
2 ms |
248 KB |
Output is correct |
8 |
Correct |
2 ms |
248 KB |
Output is correct |
9 |
Correct |
2 ms |
376 KB |
Output is correct |
10 |
Correct |
2 ms |
376 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
2 ms |
376 KB |
Output is correct |
13 |
Correct |
2 ms |
248 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
248 KB |
Output is correct |
2 |
Correct |
2 ms |
248 KB |
Output is correct |
3 |
Correct |
2 ms |
248 KB |
Output is correct |
4 |
Correct |
2 ms |
248 KB |
Output is correct |
5 |
Correct |
2 ms |
248 KB |
Output is correct |
6 |
Correct |
2 ms |
380 KB |
Output is correct |
7 |
Correct |
2 ms |
248 KB |
Output is correct |
8 |
Correct |
2 ms |
248 KB |
Output is correct |
9 |
Correct |
2 ms |
376 KB |
Output is correct |
10 |
Correct |
2 ms |
376 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
2 ms |
376 KB |
Output is correct |
13 |
Correct |
2 ms |
248 KB |
Output is correct |
14 |
Correct |
3 ms |
376 KB |
Output is correct |
15 |
Correct |
2 ms |
376 KB |
Output is correct |
16 |
Correct |
2 ms |
376 KB |
Output is correct |
17 |
Correct |
2 ms |
376 KB |
Output is correct |
18 |
Correct |
2 ms |
376 KB |
Output is correct |
19 |
Correct |
2 ms |
376 KB |
Output is correct |
20 |
Correct |
2 ms |
504 KB |
Output is correct |
21 |
Correct |
2 ms |
504 KB |
Output is correct |
22 |
Correct |
2 ms |
376 KB |
Output is correct |
23 |
Correct |
3 ms |
376 KB |
Output is correct |
24 |
Correct |
2 ms |
376 KB |
Output is correct |
25 |
Correct |
3 ms |
376 KB |
Output is correct |
26 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
248 KB |
Output is correct |
2 |
Correct |
2 ms |
248 KB |
Output is correct |
3 |
Correct |
2 ms |
248 KB |
Output is correct |
4 |
Correct |
2 ms |
248 KB |
Output is correct |
5 |
Correct |
2 ms |
248 KB |
Output is correct |
6 |
Correct |
2 ms |
380 KB |
Output is correct |
7 |
Correct |
2 ms |
248 KB |
Output is correct |
8 |
Correct |
2 ms |
248 KB |
Output is correct |
9 |
Correct |
2 ms |
376 KB |
Output is correct |
10 |
Correct |
2 ms |
376 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
2 ms |
376 KB |
Output is correct |
13 |
Correct |
2 ms |
248 KB |
Output is correct |
14 |
Correct |
3 ms |
376 KB |
Output is correct |
15 |
Correct |
2 ms |
376 KB |
Output is correct |
16 |
Correct |
2 ms |
376 KB |
Output is correct |
17 |
Correct |
2 ms |
376 KB |
Output is correct |
18 |
Correct |
2 ms |
376 KB |
Output is correct |
19 |
Correct |
2 ms |
376 KB |
Output is correct |
20 |
Correct |
2 ms |
504 KB |
Output is correct |
21 |
Correct |
2 ms |
504 KB |
Output is correct |
22 |
Correct |
2 ms |
376 KB |
Output is correct |
23 |
Correct |
3 ms |
376 KB |
Output is correct |
24 |
Correct |
2 ms |
376 KB |
Output is correct |
25 |
Correct |
3 ms |
376 KB |
Output is correct |
26 |
Correct |
2 ms |
376 KB |
Output is correct |
27 |
Correct |
6 ms |
504 KB |
Output is correct |
28 |
Correct |
6 ms |
504 KB |
Output is correct |
29 |
Correct |
7 ms |
504 KB |
Output is correct |
30 |
Correct |
6 ms |
504 KB |
Output is correct |
31 |
Correct |
5 ms |
504 KB |
Output is correct |
32 |
Correct |
7 ms |
632 KB |
Output is correct |
33 |
Correct |
10 ms |
632 KB |
Output is correct |
34 |
Correct |
11 ms |
632 KB |
Output is correct |
35 |
Correct |
10 ms |
632 KB |
Output is correct |
36 |
Correct |
5 ms |
504 KB |
Output is correct |
37 |
Correct |
16 ms |
504 KB |
Output is correct |
38 |
Correct |
17 ms |
504 KB |
Output is correct |
39 |
Correct |
12 ms |
544 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
497 ms |
1460 KB |
Output is correct |
2 |
Correct |
571 ms |
1772 KB |
Output is correct |
3 |
Correct |
595 ms |
1616 KB |
Output is correct |
4 |
Correct |
608 ms |
1668 KB |
Output is correct |
5 |
Correct |
261 ms |
1432 KB |
Output is correct |
6 |
Correct |
285 ms |
1520 KB |
Output is correct |
7 |
Correct |
440 ms |
2072 KB |
Output is correct |
8 |
Correct |
444 ms |
2428 KB |
Output is correct |
9 |
Correct |
455 ms |
2384 KB |
Output is correct |
10 |
Correct |
461 ms |
2396 KB |
Output is correct |
11 |
Correct |
528 ms |
2380 KB |
Output is correct |
12 |
Correct |
473 ms |
1776 KB |
Output is correct |
13 |
Correct |
211 ms |
1456 KB |
Output is correct |
14 |
Correct |
364 ms |
1852 KB |
Output is correct |
15 |
Correct |
268 ms |
1924 KB |
Output is correct |
16 |
Correct |
349 ms |
1972 KB |
Output is correct |
17 |
Correct |
461 ms |
2324 KB |
Output is correct |
18 |
Execution timed out |
2680 ms |
8000 KB |
Time limit exceeded |
19 |
Halted |
0 ms |
0 KB |
- |