oj.uz

답안 #201422

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
201422 2020-02-10T14:30:36 Z BThero Meetings (JOI19_meetings) C++17
0 / 100
 97 ms 680 KB 
// Why am I so dumb? :c
// chrono::system_clock::now().time_since_epoch().count()
                                                  
#include<bits/stdc++.h>
#include "meetings.h"
//#include<ext/pb_ds/assoc_container.hpp>
//#include<ext/pb_ds/tree_policy.hpp>

#define pb push_back
#define mp make_pair

#define all(x) (x).begin(), (x).end()

#define fi first
#define se second

using namespace std;
//using namespace __gnu_pbds;

typedef long long ll;   
typedef pair<int, int> pii;
//template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());

struct cmp {
    int x;

    cmp(int y) {
        x = y;        
    }

    bool operator()(int a, int b) {
        return Query(x, a, b) == a;
    }
};

int n;

void dfs(vector<int> S) {
    if (S.size() <= 1) {
        return;
    }

    int a = S[0];
    int b = S[1 + rnd() % (S.size() - 1)];
    vector<int> path;
    vector<vector<int> > later(n + 1);
    path.pb(a);
    path.pb(b);

    for (int c : S) {
        if (c == a || c == b) {
            continue;
        }

        int x = Query(a, b, c);

        if (x == c) {
            path.pb(c);            
        }
        else {
            later[x].pb(c);        
        }                                                                                                                                                                 
    }    

    sort(path.begin() + 1, path.end(), cmp(a));

    for (int i = 1; i < path.size(); ++i) {
        Bridge(path[i - 1], path[i]);
    }

    for (int c : S) {
        later[c].insert(later[c].begin(), c);
        dfs(later[c]);
    }                                                                                        
}

void Solve(int N) {
    n = N;
    vector<int> v;

    for (int i = 0; i < n; ++i) {
        v.pb(i);
    }

    dfs(v);
}

Compilation message

meetings.cpp: In function 'void dfs(std::vector<int>)':
meetings.cpp:69:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 1; i < path.size(); ++i) {
                     ~~^~~~~~~~~~~~~

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 376 KB Output is correct
2 Incorrect 5 ms 248 KB Wrong Answer [3]
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 376 KB Output is correct
2 Incorrect 5 ms 248 KB Wrong Answer [3]
3 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 376 KB Output is correct
2 Incorrect 5 ms 248 KB Wrong Answer [3]
3 Halted 0 ms 0 KB -

Subtask #4
0 / 71.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 97 ms 680 KB Wrong Answer [3]
2 Halted 0 ms 0 KB -