oj.uz

Submission #702544

# Submission time Handle Problem Language Result Execution time Memory
702544 2023-02-24T10:40:37 Z alvingogo Meetings (JOI19_meetings) C++14
0 / 100
 2000 ms 7216 KB 
#include <bits/stdc++.h>
#include "meetings.h"
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;

mt19937 rnd(time(NULL));
map<pair<int,pair<int,int> >,int> mp;
int get(int a,int b,int c){
    if(a>b){
        swap(a,b);
    }
    if(b>c){
        swap(b,c);
    }
    if(a>b){
        swap(a,b);
    }
    if(a==b || b==c){
        return b;
    }
    if(mp.find({a,{b,c}})!=mp.end()){
        return mp[{a,{b,c}}];
    }
    return mp[{a,{b,c}}]=Query(a,b,c);
}
void dc(vector<int>& v){
    int n=v.size();
    if(n==1){
        return;
    }
    if(n==2){
        Bridge(min(v[0],v[1]),max(v[0],v[1]));
        return;
    }
    int x=rnd()%n;
    x=v[x];
    int y=rnd()%n;
    while(y==x){
        y=rnd()%n;
    }
    y=v[y];
    vector<int> zz;
    vector<int> gg;
    for(auto h:v){
        if(h==x){
            continue;
        }
        int u=get(x,y,h);
        if(u!=x){
            y=u;
            zz.push_back(h);
        }
        else{
            gg.push_back(h);
        }
    }
    Bridge(min(x,y),max(x,y));
    gg.push_back(x);
    dc(zz);
    dc(gg);

}
void Solve(int n){
    vector<int> v(n);
    iota(v.begin(),v.end(),0);
    dc(v);
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 1 ms 336 KB Wrong Answer [3]
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 1 ms 336 KB Wrong Answer [3]
3 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 1 ms 336 KB Wrong Answer [3]
3 Halted 0 ms 0 KB -

Subtask #4
0 / 71.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2467 ms 7216 KB Time limit exceeded
2 Halted 0 ms 0 KB -