QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#485175#8593. Coinfractal22 223ms33628kbC++172.7kb2024-07-20 14:42:352024-07-20 14:42:36

Judging History

你现在查看的是最新测评结果

  • [2024-07-20 14:42:36]
  • 评测
  • 测评结果:22
  • 用时:223ms
  • 内存:33628kb
  • [2024-07-20 14:42:35]
  • 提交

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%