oj.uz

Submission #243632

# Submission time Handle Problem Language Result Execution time Memory
243632 2020-07-01T12:52:35 Z osaaateiasavtnl Meetings (JOI19_meetings) C++14
0 / 100
 2000 ms 16364 KB 
#include "meetings.h"
#include<bits/stdc++.h>
using namespace std;
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcountll
#define ll long long
#define mp make_pair
#define f first
#define s second
#define Time (double)clock()/CLOCKS_PER_SEC
#define debug(x) std::cout << #x << ": " << x << '\n';

const int N = 2007;

int par[N];
int link[N];

int mem[N][N];
int Query(int u, int v) {
    if (mem[u][v] != -1)
        return mem[u][v];
    mem[u][v] = mem[v][u] = Query(0, u, v);
}   

bool used[N];

void Solve(int n) {
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
            mem[i][j] = -1;
                
    for (int i = 1; i < n; ++i)
        par[i] = -1;
          
    queue <int> q;
    q.push(0);
    while (q.size()) {
        int u = q.front(); q.pop();
        used[u] = 1;

        auto check = [&](int v) {
            for (int i = 0; i < n; ++i) {
                if (mem[i][v] == i && !used[i])
                    return 0;
            }   
            return 1;
        };   

        vector <int> cur;                                
        for (int v = 0; v < n; ++v) {
            if (par[v] == -1 && link[u] == link[v] && check(v)) {
                vector <bool> del(cur.size());
                bool ban = 0;
                for (int i = 0; i < cur.size(); ++i) {
                    int x = Query(v, cur[i]);
                    if (x == v) {
                        del[i] = 1;
                        link[cur[i]] = v;
                        continue;
                    }   
                    if (x == cur[i]) {
                        link[v] = cur[i];
                        ban = 1;
                        break;
                    }
                }   
                if (!ban) {
                    vector <int> a = {v};                    
                    link[v] = v;
                    for (int i = 0; i < cur.size(); ++i) {
                        if (!del[i])
                            a.app(cur[i]);
                    }
                    cur = a;
                }
            }
        }

        for (int i = 0; i < n; ++i)
            while (link[link[i]] != link[i])
                link[i] = link[link[i]];

        /*            
        cout << "link : ";
        for (int i = 0; i < n; ++i)
            cout << link[i] << ' ';
        cout << endl;
        */

        for (int v : cur) {
            par[v] = u;            
            q.push(v);
        }   
    }   

    for (int i = 1; i < n; ++i) {
        int u = i;
        int v = par[i];
        if (v < u)
            swap(u, v);

        #ifdef HOME
        //cout << "edge " << u << ' ' << v << endl;
        #endif

        Bridge(u,v);
    }   
}

Compilation message

meetings.cpp: In function 'void Solve(int)':
meetings.cpp:56:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for (int i = 0; i < cur.size(); ++i) {
                                 ~~^~~~~~~~~~~~
meetings.cpp:72:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                     for (int i = 0; i < cur.size(); ++i) {
                                     ~~^~~~~~~~~~~~
meetings.cpp: In function 'int Query(int, int)':
meetings.cpp:25:1: warning: control reaches end of non-void function [-Wreturn-type]
 }   
 ^

Subtask #1
0 / 7.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 12.0

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

Subtask #4
0 / 71.0

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