# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
208776 |
2020-03-12T07:22:02 Z |
erd1 |
Meetings (JOI19_meetings) |
C++14 |
|
862 ms |
892 KB |
#include<utility>
#include<vector>
#include<algorithm>
#include<numeric>
#include<queue>
#include<iostream>
#include<map>
#include<set>
using namespace std;
typedef int64_t lld;
typedef pair<int,int> pii;
typedef pair<lld,lld> pll;
typedef pair<int,pll> pip;
typedef pair<pll,int> ppi;
typedef pair<lld,pll> plp;
typedef pair<pll,lld> ppl;
typedef pair<pll,pll> ppp;
template<typename T>
using maxHeap = priority_queue<T,vector<T>,less<T>>;
template<typename T>
using minHeap = priority_queue<T,vector<T>,greater<T>>;
#define ff first
#define ss second
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define endl '\n'
#define jizz cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
inline void input(int &_x) {
_x = 0;
int _tmp = 1; char _tc = getchar();
while((_tc < '0' || _tc > '9') && _tc != '-') _tc = getchar();
if(_tc == '-') _tc = getchar(), _tmp = -1;
while(_tc >= '0' && _tc <= '9') _x = _x*10+(_tc-48), _tc = getchar();
_x *= _tmp;
}
inline void output(int _x) {
char _buff[20]; int _f = 0;
if(_x == 0)putchar('0');
while(_x > 0)
{
_buff[_f++] = _x%10+'0';
_x /= 10;
}
for(_f-=1; _f >= 0; _f--)
putchar(_buff[_f]);
putchar('\n');
}
template<typename Iter>
ostream& _out(ostream &s, Iter b, Iter e) {
s<<"[";
for ( auto it=b; it!=e; it++ ) s<<(it==b?"":" ")<<*it;
s<<"]";
return s;
}
template<class T1,class T2>
ostream& operator<<(ostream& out, pair<T1,T2> p) {
return out << '(' << p.first << ", " << p.second << ')';
}
template<typename T>
ostream& operator <<( ostream &s, const vector<T> &c ) {
return _out(s,c.begin(),c.end());
}
#ifdef erd1
#define pprint(x) cerr<<__PRETTY_FUNCTION__<<":"<<__LINE__<<" - "<<(#x)<<"="<<(x)<<endl
#else
#define pprint(x)
#endif
// code starts here
int Query(int, int, int);
void Bridge(int, int);
int query(int a, int b, int c){
static int x = 0;
if(++x > 40000)exit(0);
return Query(a, b, c);
}
inline void bridge(int i, int j){
//cout << i << " " << j << endl;
Bridge(min(i, j), max(i, j));
}
int curr = 0, biggest = -1;
struct comp {
bool operator()(int a, int b){
if(a == b)return false;
if(a == curr)return true;
if(b == curr)return false;
if(a == biggest)return false;
if(b == biggest)return true;
return query(curr, a, b) == a;
}
};
inline void insert(set<int, comp>& s, int a){
biggest = a, s.insert(a), biggest = -1;
}
void solve(int r, vector<int>& v){
//cout << r << v << endl;
if(v.size() == 1) return bridge(r, v[0]);
if(v.size() <= 1) return;
curr = r;
map<int, vector<int>> m; set<int, comp> ch;
m[r], m[v[0]];
ch.insert(r); insert(ch, v[0]);
for(int cur = v[0], i = 1; i < v.size(); i++){
int x = query(r, cur, v[i]);
if(x == cur){
if(m.find(cur) == m.end())
m[cur], insert(ch, cur);
cur = v[i];
} else {
if(m.find(x) == m.end())
m[x], ch.insert(x);
if(x != v[i])
m[x].pb(v[i]);
}
if(i == v.size()-1)
if(m.find(cur) == m.end())
m[cur], insert(ch, cur);
}
for(auto& i: m)
if(i.ss.size())solve(r = i.ff, i.ss);
for(auto it1 = ch.begin(), it2 = next(it1); it2 != ch.end(); it1++, it2++)
bridge(*it1, *it2);
}
void Solve(int N){
vector<int> v(N);
srand((intptr_t)(void*)new int());
iota(all(v), 0);
random_shuffle(all(v));
int x = v.back(); v.pop_back();
solve(x, v);
}
Compilation message
meetings.cpp: In function 'void solve(int, std::vector<int>&)':
meetings.cpp:108:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int cur = v[0], i = 1; i < v.size(); i++){
~~^~~~~~~~~~
meetings.cpp:120:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(i == v.size()-1)
~~^~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
248 KB |
Output is correct |
2 |
Correct |
5 ms |
376 KB |
Output is correct |
3 |
Correct |
5 ms |
376 KB |
Output is correct |
4 |
Correct |
5 ms |
248 KB |
Output is correct |
5 |
Correct |
5 ms |
376 KB |
Output is correct |
6 |
Correct |
5 ms |
376 KB |
Output is correct |
7 |
Correct |
4 ms |
248 KB |
Output is correct |
8 |
Correct |
5 ms |
376 KB |
Output is correct |
9 |
Correct |
5 ms |
376 KB |
Output is correct |
10 |
Correct |
5 ms |
248 KB |
Output is correct |
11 |
Correct |
5 ms |
248 KB |
Output is correct |
12 |
Correct |
5 ms |
252 KB |
Output is correct |
13 |
Correct |
5 ms |
248 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
248 KB |
Output is correct |
2 |
Correct |
5 ms |
376 KB |
Output is correct |
3 |
Correct |
5 ms |
376 KB |
Output is correct |
4 |
Correct |
5 ms |
248 KB |
Output is correct |
5 |
Correct |
5 ms |
376 KB |
Output is correct |
6 |
Correct |
5 ms |
376 KB |
Output is correct |
7 |
Correct |
4 ms |
248 KB |
Output is correct |
8 |
Correct |
5 ms |
376 KB |
Output is correct |
9 |
Correct |
5 ms |
376 KB |
Output is correct |
10 |
Correct |
5 ms |
248 KB |
Output is correct |
11 |
Correct |
5 ms |
248 KB |
Output is correct |
12 |
Correct |
5 ms |
252 KB |
Output is correct |
13 |
Correct |
5 ms |
248 KB |
Output is correct |
14 |
Correct |
5 ms |
376 KB |
Output is correct |
15 |
Correct |
5 ms |
376 KB |
Output is correct |
16 |
Correct |
5 ms |
380 KB |
Output is correct |
17 |
Correct |
5 ms |
376 KB |
Output is correct |
18 |
Correct |
5 ms |
248 KB |
Output is correct |
19 |
Correct |
5 ms |
376 KB |
Output is correct |
20 |
Correct |
5 ms |
376 KB |
Output is correct |
21 |
Correct |
5 ms |
376 KB |
Output is correct |
22 |
Correct |
5 ms |
376 KB |
Output is correct |
23 |
Correct |
5 ms |
376 KB |
Output is correct |
24 |
Correct |
5 ms |
248 KB |
Output is correct |
25 |
Correct |
5 ms |
248 KB |
Output is correct |
26 |
Correct |
5 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
248 KB |
Output is correct |
2 |
Correct |
5 ms |
376 KB |
Output is correct |
3 |
Correct |
5 ms |
376 KB |
Output is correct |
4 |
Correct |
5 ms |
248 KB |
Output is correct |
5 |
Correct |
5 ms |
376 KB |
Output is correct |
6 |
Correct |
5 ms |
376 KB |
Output is correct |
7 |
Correct |
4 ms |
248 KB |
Output is correct |
8 |
Correct |
5 ms |
376 KB |
Output is correct |
9 |
Correct |
5 ms |
376 KB |
Output is correct |
10 |
Correct |
5 ms |
248 KB |
Output is correct |
11 |
Correct |
5 ms |
248 KB |
Output is correct |
12 |
Correct |
5 ms |
252 KB |
Output is correct |
13 |
Correct |
5 ms |
248 KB |
Output is correct |
14 |
Correct |
5 ms |
376 KB |
Output is correct |
15 |
Correct |
5 ms |
376 KB |
Output is correct |
16 |
Correct |
5 ms |
380 KB |
Output is correct |
17 |
Correct |
5 ms |
376 KB |
Output is correct |
18 |
Correct |
5 ms |
248 KB |
Output is correct |
19 |
Correct |
5 ms |
376 KB |
Output is correct |
20 |
Correct |
5 ms |
376 KB |
Output is correct |
21 |
Correct |
5 ms |
376 KB |
Output is correct |
22 |
Correct |
5 ms |
376 KB |
Output is correct |
23 |
Correct |
5 ms |
376 KB |
Output is correct |
24 |
Correct |
5 ms |
248 KB |
Output is correct |
25 |
Correct |
5 ms |
248 KB |
Output is correct |
26 |
Correct |
5 ms |
376 KB |
Output is correct |
27 |
Correct |
12 ms |
376 KB |
Output is correct |
28 |
Correct |
10 ms |
376 KB |
Output is correct |
29 |
Correct |
12 ms |
504 KB |
Output is correct |
30 |
Correct |
10 ms |
376 KB |
Output is correct |
31 |
Correct |
9 ms |
376 KB |
Output is correct |
32 |
Correct |
13 ms |
376 KB |
Output is correct |
33 |
Correct |
18 ms |
376 KB |
Output is correct |
34 |
Correct |
20 ms |
376 KB |
Output is correct |
35 |
Correct |
19 ms |
504 KB |
Output is correct |
36 |
Correct |
10 ms |
376 KB |
Output is correct |
37 |
Correct |
20 ms |
504 KB |
Output is correct |
38 |
Correct |
18 ms |
504 KB |
Output is correct |
39 |
Correct |
18 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
556 ms |
868 KB |
Output is correct |
2 |
Correct |
534 ms |
632 KB |
Output is correct |
3 |
Correct |
572 ms |
632 KB |
Output is correct |
4 |
Correct |
555 ms |
760 KB |
Output is correct |
5 |
Correct |
403 ms |
760 KB |
Output is correct |
6 |
Correct |
409 ms |
632 KB |
Output is correct |
7 |
Correct |
667 ms |
760 KB |
Output is correct |
8 |
Correct |
761 ms |
760 KB |
Output is correct |
9 |
Correct |
717 ms |
760 KB |
Output is correct |
10 |
Correct |
662 ms |
760 KB |
Output is correct |
11 |
Correct |
789 ms |
888 KB |
Output is correct |
12 |
Correct |
390 ms |
760 KB |
Output is correct |
13 |
Correct |
369 ms |
892 KB |
Output is correct |
14 |
Correct |
521 ms |
632 KB |
Output is correct |
15 |
Correct |
489 ms |
632 KB |
Output is correct |
16 |
Correct |
459 ms |
760 KB |
Output is correct |
17 |
Correct |
713 ms |
632 KB |
Output is correct |
18 |
Correct |
449 ms |
632 KB |
Output is correct |
19 |
Correct |
470 ms |
632 KB |
Output is correct |
20 |
Correct |
557 ms |
632 KB |
Output is correct |
21 |
Correct |
601 ms |
760 KB |
Output is correct |
22 |
Correct |
591 ms |
632 KB |
Output is correct |
23 |
Correct |
570 ms |
632 KB |
Output is correct |
24 |
Correct |
557 ms |
632 KB |
Output is correct |
25 |
Correct |
533 ms |
760 KB |
Output is correct |
26 |
Correct |
623 ms |
632 KB |
Output is correct |
27 |
Correct |
603 ms |
640 KB |
Output is correct |
28 |
Correct |
862 ms |
632 KB |
Output is correct |
29 |
Correct |
694 ms |
760 KB |
Output is correct |
30 |
Correct |
693 ms |
888 KB |
Output is correct |
31 |
Incorrect |
850 ms |
760 KB |
DO NOT PRINT ANYTHING TO STANDARD OUTPUT |
32 |
Halted |
0 ms |
0 KB |
- |