# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
243627 | 2020-07-01T12:42:37 Z | osaaateiasavtnl | Meetings (JOI19_meetings) | C++14 | 1510 ms | 16484 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 nu[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); if (mem[u][v] == u) ++nu[v]; if (mem[u][v] == v) ++nu[u]; } 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(); for (int v = 0; v < n; ++v) { if (mem[u][v] == u) { --nu[v]; } } vector <int> cur; for (int v = 0; v < n; ++v) { if (par[v] == -1 && link[u] == link[v] && nu[v] == 0) { 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 | 13 ms | 16128 KB | Output is correct |
2 | Correct | 13 ms | 16128 KB | Output is correct |
3 | Correct | 13 ms | 16128 KB | Output is correct |
4 | Correct | 15 ms | 16128 KB | Output is correct |
5 | Correct | 15 ms | 16128 KB | Output is correct |
6 | Incorrect | 15 ms | 16128 KB | Wrong Answer [3] |
7 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 13 ms | 16128 KB | Output is correct |
2 | Correct | 13 ms | 16128 KB | Output is correct |
3 | Correct | 13 ms | 16128 KB | Output is correct |
4 | Correct | 15 ms | 16128 KB | Output is correct |
5 | Correct | 15 ms | 16128 KB | Output is correct |
6 | Incorrect | 15 ms | 16128 KB | Wrong Answer [3] |
7 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 13 ms | 16128 KB | Output is correct |
2 | Correct | 13 ms | 16128 KB | Output is correct |
3 | Correct | 13 ms | 16128 KB | Output is correct |
4 | Correct | 15 ms | 16128 KB | Output is correct |
5 | Correct | 15 ms | 16128 KB | Output is correct |
6 | Incorrect | 15 ms | 16128 KB | Wrong Answer [3] |
7 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1510 ms | 16484 KB | Wrong Answer [3] |
2 | Halted | 0 ms | 0 KB | - |