QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#485175 | #8593. Coin | fractal | 22 | 223ms | 33628kb | C++17 | 2.7kb | 2024-07-20 14:42:35 | 2024-07-20 14:42:36 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define make_unique(x) sort(all(x)), x.erase(unique(all(x)), x.end())
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 Rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int N = 1e6 + 200;
const int M = 1e6;
const int inf = 2e9 + 3;
const ll INF = 1e18;
int n, m;
vector<int> g[N];
int can[1001][1001];
int ans[N], now[N], d[N];
int sz = 0;
int u[N], C, pos[N];
void dfs(int v) {
u[v] = C;
for (auto to : g[v]) {
if (u[to] == C) continue;
dfs(to);
}
++sz;
if (pos[v] && pos[v] != sz) {
ans[v] = -1;
}
pos[v] = sz;
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; ++i)
ans[i] = -1;
if (n <= 100) {
vector<int> Ans(n + 1, -1);
for (int i = 1, x, y; i <= m; ++i) {
cin >> x >> y;
g[x].push_back(y);
for (int j = 1; j <= n; ++j) {
ans[j] = i;
pos[j] = 0;
}
int T = 200;
while (T--) {
vector<int> v(n);
iota(v.begin(), v.end(), 1);
shuffle(v.begin(), v.end(), rng);
for (int j = 1; j <= n; ++j)
shuffle(g[j].begin(), g[j].end(), rng);
++C;
sz = 0;
for (int j : v) {
if (u[j] != C) {
dfs(j);
}
}
}
for (int j = 1; j <= n; ++j) {
if (ans[j] == i && Ans[j] == -1) Ans[j] = i;
}
}
for (int i = 1; i <= n; ++i)
cout << Ans[i] << " \n"[i == n];
return 0;
}
for (int i = 1, x, y; i <= m; ++i) {
cin >> x >> y;
g[x].push_back(y);
d[y]++;
}
C = 1;
for (int i = 1; i <= n; ++i) {
ans[i] = m;
if (u[i] == 0) {
dfs(i);
}
}
int T = 100;
while (T--) {
vector<int> v(n);
iota(v.begin(), v.end(), 1);
shuffle(v.begin(), v.end(), rng);
for (int i = 1; i <= n; ++i)
shuffle(g[i].begin(), g[i].end(), rng);
++C;
sz = 0;
for (int i : v) {
if (u[i] != C) {
dfs(i);
}
}
}
for (int i = 1; i <= n; ++i)
cout << ans[i] << " \n"[i == n];
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 6
Accepted
Test #1:
score: 6
Accepted
time: 0ms
memory: 31512kb
input:
4 4 2 4 3 1 4 1 2 3
output:
3 4 -1 -1
result:
ok ac
Test #2:
score: 6
Accepted
time: 0ms
memory: 31740kb
input:
6 8 1 5 5 4 6 2 2 5 4 3 6 1 6 5 2 1
output:
8 8 5 5 5 6
result:
ok ac
Test #3:
score: 6
Accepted
time: 6ms
memory: 31496kb
input:
2 1 1 2
output:
1 1
result:
ok ac
Test #4:
score: 6
Accepted
time: 0ms
memory: 32848kb
input:
6 12 1 5 5 4 6 2 2 5 4 3 6 5 1 5 1 5 2 4 6 3 1 3 4 3
output:
-1 -1 5 5 5 -1
result:
ok ac
Test #5:
score: 6
Accepted
time: 2ms
memory: 32636kb
input:
7 20 1 6 6 3 1 4 1 5 1 7 1 2 1 5 2 3 4 5 7 2 2 4 5 3 6 3 1 3 4 3 7 5 2 6 4 6 7 2 7 5
output:
6 17 12 18 -1 -1 17
result:
ok ac
Test #6:
score: 6
Accepted
time: 0ms
memory: 32984kb
input:
7 20 5 6 1 3 3 6 4 1 7 4 2 5 4 3 2 6 7 5 4 6 2 6 2 1 4 5 1 3 1 5 7 1 7 6 4 1 7 6 3 6
output:
15 -1 -1 -1 -1 6 -1
result:
ok ac
Test #7:
score: 6
Accepted
time: 7ms
memory: 31256kb
input:
7 20 7 6 4 5 6 4 3 6 4 1 6 2 3 5 5 2 7 6 1 2 3 6 6 4 7 1 6 1 7 1 4 5 3 6 3 5 4 5 3 1
output:
-1 10 -1 8 -1 6 -1
result:
ok ac
Subtask #2:
score: 16
Accepted
Dependency #1:
100%
Accepted
Test #8:
score: 16
Accepted
time: 14ms
memory: 31304kb
input:
20 100 5 20 4 5 18 16 1 13 14 9 11 19 6 4 7 20 16 11 8 13 4 5 16 9 12 14 7 12 11 3 9 11 9 11 13 6 3 10 12 9 13 4 20 12 13 6 18 11 5 7 5 7 15 18 12 15 17 13 15 18 3 2 11 2 11 2 15 19 4 19 14 19 14 9 17 3 1 18 8 10 16 19 1 6 7 2 5 12 1 18 8 20 5 18 8 5 4 16 1 15 5 19 18 19 17 10 1 10 17 3 10 2 3 10 17...
output:
-1 -1 -1 31 31 31 31 -1 31 -1 31 31 31 -1 71 -1 -1 -1 -1 31
result:
ok ac
Test #9:
score: 16
Accepted
time: 223ms
memory: 32092kb
input:
100 400 87 45 42 17 9 81 65 10 8 82 76 48 39 73 21 58 76 30 76 92 74 76 99 90 38 50 86 74 75 52 8 2 80 55 20 95 66 60 78 82 10 18 22 59 23 17 63 76 56 51 38 10 50 65 41 28 64 77 59 53 100 66 38 84 23 47 17 9 45 75 41 28 33 41 8 78 2 95 3 11 40 15 60 63 23 17 82 2 61 44 44 16 77 34 100 66 96 99 68 12...
output:
-1 -1 187 -1 183 -1 -1 -1 183 -1 187 -1 -1 187 183 187 183 -1 -1 -1 -1 183 -1 183 -1 -1 183 183 -1 -1 -1 -1 187 187 -1 -1 187 183 183 183 -1 -1 183 187 183 188 -1 -1 -1 -1 183 -1 183 183 -1 -1 -1 -1 183 -1 187 -1 -1 187 -1 187 -1 -1 -1 -1 -1 -1 183 -1 183 187 187 -1 188 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1...
result:
ok ac
Subtask #3:
score: 0
Wrong Answer
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Test #10:
score: 0
Wrong Answer
time: 8ms
memory: 33628kb
input:
1000 4000 619 298 211 477 584 418 812 280 978 268 280 345 715 364 73 664 915 819 535 28 110 959 384 663 773 315 792 250 374 80 134 202 779 416 613 334 318 756 21 812 424 997 664 277 151 963 299 438 955 988 532 653 521 43 121 20 902 849 237 305 272 893 325 792 469 549 891 531 612 810 294 256 188 990 ...
output:
-1 4000 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 4000 4000 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 4000 4000 4000 -1 -1 -1 -1 4000 -1 -1 -1 -1 -1 -1 -1 4000 -1 -1 4000 4000 -1 -1 -1 -1 -1 -1 -1 -1 -1 4000 -1 -1 -1 -1 -1 -1 4000 -1 -1 -1 4000 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 4000 -1 -1 -1 -1 -1...
result:
wrong answer wa
Subtask #4:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
0%