oj.uz

Submission #154947

# Submission time Handle Problem Language Result Execution time Memory
154947 2019-09-25T15:57:38 Z Mercenary Meetings (JOI19_meetings) C++14
0 / 100
 348 ms 262148 KB 
#include "meetings.h"
#include<bits/stdc++.h>
#define pb push_back
using namespace std;

const int maxn = 2e3 + 4;
int L[maxn][maxn];

int LCA(int u , int v){
    if(u == 0 || v == 0)return 0;
    if(u == v)return u;
    if(u > v)swap(u , v);
    if(L[u][v] != -1)return L[u][v];
    return L[u][v] = Query(0 , u , v);
}

void Solve(vector<int> child){
//    for(int c : child)cout << c << " ";cout << endl;
    vector<int> v[maxn];
    srand(time(0));
    int u = child[rand() % child.size()];
    vector<int> can;
    for(int c : child){
        int a = LCA(c , u);
//        cout << u << " " << c << " " << a << endl;
        if(a == c){
            can.pb(a);
        }
        v[a].pb(c);
    }
    sort(can.begin(),can.end(),[&](const int & x , const int & y){
            return LCA(x , y) == x;
         });
    for(int i = 0 ; i < (int)can.size() - 1 ; ++i){
        Bridge(min(can[i] , can[i + 1]) , max(can[i] , can[i + 1]));
    }
    for(int c : child)if(v[c].size() > 1)Solve(v[c]);
}

void Solve(int n) {
    memset(L,-1,sizeof L);
    vector<int> v(n);
    for(int i = 0 ; i < n ; ++i)v[i] = i;
    Solve(v);
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 227 ms 225504 KB Output is correct
2 Correct 16 ms 16248 KB Output is correct
3 Runtime error 237 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 227 ms 225504 KB Output is correct
2 Correct 16 ms 16248 KB Output is correct
3 Runtime error 237 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 227 ms 225504 KB Output is correct
2 Correct 16 ms 16248 KB Output is correct
3 Runtime error 237 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #4
0 / 71.0

# Verdict Execution time Memory Grader output
1 Runtime error 348 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -