# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
243634 | 2020-07-01T12:54:15 Z | osaaateiasavtnl | Meetings (JOI19_meetings) | C++14 | 2000 ms | 16356 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
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 14 ms | 16128 KB | Output is correct |
2 | Incorrect | 13 ms | 16128 KB | Wrong Answer [4] |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 14 ms | 16128 KB | Output is correct |
2 | Incorrect | 13 ms | 16128 KB | Wrong Answer [4] |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 14 ms | 16128 KB | Output is correct |
2 | Incorrect | 13 ms | 16128 KB | Wrong Answer [4] |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 3067 ms | 16356 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |