oj.uz

Submission #375097

# Submission time Handle Problem Language Result Execution time Memory
375097 2021-03-09T02:52:34 Z wiwiho Meetings (JOI19_meetings) C++14
0 / 100
 2000 ms 1144 KB 
#include "meetings.h"
#include <bits/stdc++.h>
 
#define eb emplace_back
#define iter(a) a.begin(), a.end()
#define printv(a, b) { \
    for(auto pv : a) b << pv << " "; \
    b << "\n"; \
}
 
using namespace std;
 
typedef long long ll;  

vector<set<int>> g;

void addEdge(int a, int b){
    g[a].insert(b);
    g[b].insert(a);
}

void insertEdge(int a, int b, int v){
    g[a].erase(b);
    g[b].erase(a);
    addEdge(a, v);
    addEdge(b, v);
}

vector<int> sz, mx;
vector<int> tv;
vector<bool> del;

void dfs(int now, int p){
    sz[now] = 1;
    tv.eb(now);
    mx[now] = 0;
    for(int i : g[now]){
        if(i == p || del[i]) continue;
        dfs(i, now);
        sz[now] += sz[i];
        mx[now] = max(mx[now], sz[i]);
    }
}

void calc(int now, int qry){
    tv.clear();
    dfs(now, now);

    if(tv.size() == 1){
        addEdge(now, qry);
        //cerr << qry << " add " << now << "\n";
        return;
    }

    int gv = now;
    for(int i : tv){
        if(mx[i] <= sz[now] / 2 && sz[now] - sz[i] <= sz[now] / 2) gv = i;
    }
    //cerr << "test " << now << " " << gv << "\n";
    del[gv] = true;

    for(int i : g[gv]){
        if(del[i]) continue;
        int r = Query(i, gv, qry);
        if(r == qry){
            insertEdge(i, gv, qry);
            //cerr << qry << " insert " << i << " " << gv << "\n";
            return;
        }
        else if(r == i){
            calc(i, qry);
            return;
        }
    }
    addEdge(gv, qry);
    //cerr << qry << " gv " << gv << "\n";
}

void Solve(int n){
    
    sz.resize(n);
    mx.resize(n);
    del.resize(n);
    g.resize(n);

    addEdge(0, 1);

    for(int i = 2; i < n; i++){
        fill(iter(del), false);
        calc(0, i);
    }

//    for(int i = 0; i < n; i++){
//        cerr << i << "  ";
//        printv(g[i], cerr);
//    }

    for(int i = 0; i < n; i++){
        for(int j : g[i]){
            if(i < j){
                //cerr << i << " " << j << "\n";
                Bridge(i, j);
            }
        }
    }

}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Incorrect 1 ms 364 KB Wrong Answer [4]
7 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Incorrect 1 ms 364 KB Wrong Answer [4]
7 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Incorrect 1 ms 364 KB Wrong Answer [4]
7 Halted 0 ms 0 KB -

Subtask #4
0 / 71.0

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