oj.uz

Submission #760657

# Submission time Handle Problem Language Result Execution time Memory
760657 2023-06-18T05:10:39 Z Magikarp4000 Stray Cat (JOI20_stray) C++17
89 / 100
 331 ms 524288 KB 
#include "Anthony.h"
#include <bits/stdc++.h>
using namespace std;
#define OPTM ios_base::sync_with_stdio(0); cin.tie(0);
#define INF int(1e9+7)
#define ln '\n' 
#define ll long long
#define ull unsigned long long
#define ui unsigned int
#define us unsigned short
#define FOR(i,s,n) for (int i = s; i < n; i++)
#define FORR(i,n,s) for (int i = n; i > s; i--)
#define FORX(u, arr) for (auto u : arr)
#define PB push_back
#define in(v,x) (v.find(x) != v.end())
#define F first
#define S second
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define UM unordered_map
#define US unordered_set
#define PQ priority_queue
#define ALL(v) v.begin(), v.end()
const ll LLINF = 1e18+1;

const int pat[] = {1,1,0,1,0,0};

const int MAXN = 2e4+1;
int n,m;
vector<PII> v[MAXN];
int p[MAXN], pr[MAXN];
vector<int> res;
int d[MAXN], a[MAXN];

namespace {
    void dfs(int s, int pa) {
        if (s != 0 && v[s].size() >= 3) {
            int c = res[pr[s]] == 1 ? 0 : 1;
            FORX(u,v[s]) {
                if (u.F == pa) continue;
                res[u.S] = c;
            }
            if (res[pr[s]] == -1) res[pr[s]] = 0;
        }
        FORX(u,v[s]) {
            if (u.F == pa) continue;
            pr[u.F] = s;
            pr[u.F] = u.S;
            dfs(u.F,s);
        }
    }

    void dfs1(int s, int pa, int idx) {
        FORX(u,v[s]) {
            if (u.F == pa) continue;
            int nc = idx;
            if ((s == 0 || v[s].size() == 2) && res[u.S] == -1) {
                res[u.S] = pat[idx];
                nc = (idx+1)%6;
            }
            if (v[s].size() >= 3) nc = 0;
            dfs1(u.F,s,nc);
        }
    }

    void dfs2(int s, int pa, int val) {
        FORX(u,v[s]) {
            if (u.F == pa) continue;
            res[u.S] = val;
            dfs2(u.F,s,(val+1)%3);
        }
    }
} // namespace

void sub2() {
    queue<PII> q;
    FOR(i,0,n) d[i] = INF;
    d[0] = 0;
    q.push({0,0});
    while (!q.empty()) {
        int s = q.front().F, val = q.front().S;
        q.pop();
        FORX(u,v[s]) {
            if (d[s]+1 < d[u.F]) {
                d[u.F] = d[s]+1;
                res[u.S] = val;
                a[u.F] = val;
                q.push({u.F,(val+1)%3});
            }
        }
    }
    FOR(i,1,n) {
        FORX(u,v[i]) {
            if (res[u.S] == -1) {
                res[u.S] = 4;
            }
        }
    }
}

void sub3() {
    dfs2(0,-1,0);
}

void sub7() {
    dfs(0,-1);
    dfs1(0,-1,0);
}

std::vector<int> Mark(int N, int M, int A, int B, std::vector<int> U, std::vector<int> V) {
    n = N; m = M;
    FOR(i,0,m) {
        v[U[i]].PB({V[i],i});
        v[V[i]].PB({U[i],i});
    }
    FOR(i,0,m) res.PB(-1);
    if (A == 2) sub7();
    else if (A == 3) sub3();
    else if (A == 4) sub2();
    // FOR(i,0,m) cout << res[i] << ' ';
    // cout << ln;
    return res;
}

#include "Catherine.h"
using namespace std;
#define OPTM ios_base::sync_with_stdio(0); cin.tie(0);
#define INF int(1e9+7)
#define ln '\n' 
#define ll long long
#define ull unsigned long long
#define ui unsigned int
#define us unsigned short
#define FOR(i,s,n) for (int i = s; i < n; i++)
#define FORR(i,n,s) for (int i = n; i > s; i--)
#define FORX(u, arr) for (auto u : arr)
#define PB push_back
#define in(v,x) (v.find(x) != v.end())
#define F first
#define S second
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define UM unordered_map
#define US unordered_set
#define PQ priority_queue
#define ALL(v) v.begin(), v.end()
const ll LLINF = 1e18+1;

namespace {
    int A, B;
    bool flag = 0;
    PII start = {-1,-1}, turn = {0,0};
    bool done = 0;
    int pre = -1;

    int bruh(int x) {
        if (x != -1) pre = x;
        return x;
    }
} // namespace

void Init(int A, int B)
{
    ::A = A;
    ::B = B;
}

int sub7(std::vector<int> y) {
    int c0 = y[0], c1 = y[1];
    if (pre == 0) c0++;
    else if (pre == 1) c1++;
    if (c0+c1 == 1) {
        flag = 1;
        if (y[0]) return bruh(0);
        if (y[1]) return bruh(1);
        return bruh(-1);
    }
    if (c0+c1 >= 3) {
        flag = 1;
        if (c0 == 1) {
            if (y[0] == 1) return bruh(0);
            return bruh(-1);
        }
        else if (c1 == 1) {
            if (y[1] == 1) return bruh(1);
            return bruh(-1);
        }
    }
    if (flag) return y[0] == 1 ? bruh(0) : bruh(1);
    if (start == make_pair(-1,-1)) {
        start.F = (c0 == 2 || c1 == 2) ? 2 : 1;
        start.S = (c1 == 2) ? 1 : 0;
        turn.F++;
        pre = start.S;
        return bruh(start.S);
    }
    bool db = (c0 == 2 || c1 == 2) ? 1 : 0;
    int val = y[0] == 1 ? 0 : 1;
    if (start == make_pair(2,0)) {
        if (turn.F == 2) {
            flag = 1;
            return db ? bruh(-1) : bruh(val);
        }
        else {
            turn.F++;
            return bruh(val);
        }
    }
    else if (start == make_pair(2,1)) {
        if (turn.F == 2) {
            flag = 1;
            return db ? bruh(val) : bruh(-1);
        }
        else {
            turn.F++;
            return bruh(val);
        }
    }
    else {
        if (turn.F == 2) {
            flag = 1;
            return db ? bruh(val) : bruh(-1);
        }
        else if (turn.F == 1) {
            if (!done) {
                if (!db) {
                    turn.F++;
                    return bruh(val);
                }
                else {
                    done = 1;
                    turn.S++;
                    return bruh(-1);
                }
            }
            else {
                if (turn.S == 2) {
                    flag = 1;
                    return db ? bruh(-1) : bruh(val);
                }
                else {
                    turn.S++;
                    return bruh(val);
                }
            }
        }
    }
}

int sub3(std::vector<int> y) {
    int c[3] = {0,0,0};
    FOR(i,0,3) c[i] += y[i];
    if (pre != -1) c[pre]++;
    if (c[0] && c[1]) return bruh(0);
    if (c[1] && c[2]) return bruh(1);
    if (c[2] && c[0]) return bruh(2);
    FOR(i,0,3) if (c[i]) return bruh(i);
}

int Move(std::vector<int> y) {
    if (A == 2) return sub7(y);
    else if (A == 3) return sub3(y);
    else if (A == 4) return sub3(y);
}

Compilation message

Catherine.cpp: In function 'int sub7(std::vector<int>)':
Catherine.cpp:124:1: warning: control reaches end of non-void function [-Wreturn-type]
  124 | }
      | ^
Catherine.cpp: In function 'int sub3(std::vector<int>)':
Catherine.cpp:134:1: warning: control reaches end of non-void function [-Wreturn-type]
  134 | }
      | ^
Catherine.cpp: In function 'int Move(std::vector<int>)':
Catherine.cpp:140:1: warning: control reaches end of non-void function [-Wreturn-type]
  140 | }
      | ^

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 15636 KB Output is correct
2 Correct 2 ms 1024 KB Output is correct
3 Correct 24 ms 14932 KB Output is correct
4 Correct 35 ms 16616 KB Output is correct
5 Correct 36 ms 16696 KB Output is correct
6 Correct 28 ms 15380 KB Output is correct
7 Correct 27 ms 15496 KB Output is correct
8 Correct 31 ms 16180 KB Output is correct
9 Correct 32 ms 16280 KB Output is correct

Subtask #2
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 15636 KB Output is correct
2 Correct 2 ms 1024 KB Output is correct
3 Correct 24 ms 14932 KB Output is correct
4 Correct 35 ms 16616 KB Output is correct
5 Correct 36 ms 16696 KB Output is correct
6 Correct 28 ms 15380 KB Output is correct
7 Correct 27 ms 15496 KB Output is correct
8 Correct 31 ms 16180 KB Output is correct
9 Correct 32 ms 16280 KB Output is correct
10 Incorrect 6 ms 2452 KB Wrong Answer [2]
11 Halted 0 ms 0 KB -

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 13712 KB Output is correct
2 Correct 1 ms 1032 KB Output is correct
3 Correct 20 ms 12660 KB Output is correct
4 Correct 32 ms 15576 KB Output is correct
5 Correct 37 ms 15552 KB Output is correct
6 Correct 26 ms 13420 KB Output is correct
7 Correct 27 ms 13280 KB Output is correct
8 Correct 30 ms 14644 KB Output is correct
9 Correct 30 ms 14596 KB Output is correct
10 Correct 28 ms 14216 KB Output is correct
11 Correct 28 ms 14328 KB Output is correct
12 Correct 28 ms 14264 KB Output is correct
13 Correct 28 ms 14224 KB Output is correct
14 Correct 30 ms 14696 KB Output is correct
15 Correct 31 ms 14424 KB Output is correct

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 13712 KB Output is correct
2 Correct 1 ms 1032 KB Output is correct
3 Correct 20 ms 12660 KB Output is correct
4 Correct 32 ms 15576 KB Output is correct
5 Correct 37 ms 15552 KB Output is correct
6 Correct 26 ms 13420 KB Output is correct
7 Correct 27 ms 13280 KB Output is correct
8 Correct 30 ms 14644 KB Output is correct
9 Correct 30 ms 14596 KB Output is correct
10 Correct 28 ms 14216 KB Output is correct
11 Correct 28 ms 14328 KB Output is correct
12 Correct 28 ms 14264 KB Output is correct
13 Correct 28 ms 14224 KB Output is correct
14 Correct 30 ms 14696 KB Output is correct
15 Correct 31 ms 14424 KB Output is correct
16 Runtime error 331 ms 524288 KB Execution killed with signal 9
17 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1348 KB Output is correct
2 Correct 1 ms 1036 KB Output is correct
3 Correct 1 ms 1288 KB Output is correct
4 Correct 2 ms 1416 KB Output is correct
5 Correct 3 ms 1420 KB Output is correct
6 Correct 2 ms 1292 KB Output is correct
7 Correct 2 ms 1424 KB Output is correct
8 Correct 2 ms 1416 KB Output is correct
9 Correct 2 ms 1404 KB Output is correct
10 Correct 2 ms 1416 KB Output is correct
11 Correct 2 ms 1416 KB Output is correct
12 Correct 1 ms 1288 KB Output is correct
13 Correct 2 ms 1292 KB Output is correct
14 Correct 1 ms 1344 KB Output is correct
15 Correct 1 ms 1288 KB Output is correct
16 Correct 2 ms 1292 KB Output is correct
17 Correct 1 ms 1288 KB Output is correct
18 Correct 2 ms 1288 KB Output is correct
19 Correct 2 ms 1288 KB Output is correct
20 Correct 1 ms 1288 KB Output is correct
21 Correct 2 ms 1296 KB Output is correct
22 Correct 2 ms 1348 KB Output is correct
23 Correct 1 ms 1296 KB Output is correct
24 Correct 1 ms 1296 KB Output is correct
25 Correct 2 ms 1292 KB Output is correct
26 Correct 2 ms 1296 KB Output is correct
27 Correct 2 ms 1300 KB Output is correct
28 Correct 1 ms 1288 KB Output is correct

Subtask #6
71.0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 11524 KB Output is correct
2 Correct 27 ms 12692 KB Output is correct
3 Correct 1 ms 1028 KB Output is correct
4 Correct 20 ms 11444 KB Output is correct
5 Correct 34 ms 14216 KB Output is correct
6 Correct 32 ms 14384 KB Output is correct
7 Correct 30 ms 13324 KB Output is correct
8 Correct 27 ms 13424 KB Output is correct
9 Correct 32 ms 14220 KB Output is correct
10 Correct 32 ms 14300 KB Output is correct
11 Correct 40 ms 14264 KB Output is correct
12 Correct 33 ms 14272 KB Output is correct
13 Correct 32 ms 14184 KB Output is correct
14 Correct 35 ms 14168 KB Output is correct
15 Correct 33 ms 14316 KB Output is correct
16 Correct 31 ms 14300 KB Output is correct
17 Correct 37 ms 14036 KB Output is correct
18 Correct 30 ms 13984 KB Output is correct
19 Correct 30 ms 13984 KB Output is correct
20 Correct 28 ms 13936 KB Output is correct
21 Correct 28 ms 13980 KB Output is correct
22 Correct 30 ms 13972 KB Output is correct
23 Correct 25 ms 11440 KB Output is correct
24 Correct 25 ms 11560 KB Output is correct
25 Correct 28 ms 11900 KB Output is correct
26 Correct 25 ms 12008 KB Output is correct
27 Correct 30 ms 12708 KB Output is correct
28 Correct 28 ms 12824 KB Output is correct
29 Correct 28 ms 12800 KB Output is correct
30 Correct 30 ms 12848 KB Output is correct
31 Correct 25 ms 11496 KB Output is correct
32 Correct 25 ms 11568 KB Output is correct
33 Correct 26 ms 11976 KB Output is correct
34 Correct 26 ms 11924 KB Output is correct
35 Correct 28 ms 12664 KB Output is correct
36 Correct 28 ms 12716 KB Output is correct
37 Correct 30 ms 12784 KB Output is correct
38 Correct 35 ms 12652 KB Output is correct
39 Correct 27 ms 12688 KB Output is correct
40 Correct 27 ms 12768 KB Output is correct
41 Correct 30 ms 13284 KB Output is correct
42 Correct 30 ms 13372 KB Output is correct
43 Correct 28 ms 13356 KB Output is correct
44 Correct 43 ms 13336 KB Output is correct
45 Correct 30 ms 13296 KB Output is correct
46 Correct 30 ms 13284 KB Output is correct
47 Correct 27 ms 12524 KB Output is correct
48 Correct 28 ms 12476 KB Output is correct
49 Correct 27 ms 12388 KB Output is correct
50 Correct 28 ms 12520 KB Output is correct
51 Correct 25 ms 11400 KB Output is correct
52 Correct 25 ms 11528 KB Output is correct
53 Correct 28 ms 11480 KB Output is correct
54 Correct 25 ms 11452 KB Output is correct
55 Correct 25 ms 11596 KB Output is correct
56 Correct 25 ms 11520 KB Output is correct
57 Correct 25 ms 11420 KB Output is correct
58 Correct 26 ms 11500 KB Output is correct
59 Correct 25 ms 11676 KB Output is correct
60 Correct 26 ms 11612 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 11440 KB Output is correct
2 Correct 30 ms 12568 KB Output is correct
3 Correct 1 ms 1036 KB Output is correct
4 Correct 20 ms 11308 KB Output is correct
5 Correct 33 ms 14228 KB Output is correct
6 Correct 32 ms 14212 KB Output is correct
7 Correct 28 ms 13316 KB Output is correct
8 Correct 28 ms 13340 KB Output is correct
9 Correct 34 ms 14312 KB Output is correct
10 Correct 32 ms 14240 KB Output is correct
11 Correct 31 ms 14192 KB Output is correct
12 Correct 34 ms 14232 KB Output is correct
13 Correct 31 ms 14256 KB Output is correct
14 Correct 31 ms 14272 KB Output is correct
15 Correct 31 ms 14296 KB Output is correct
16 Correct 31 ms 14260 KB Output is correct
17 Correct 30 ms 13956 KB Output is correct
18 Correct 32 ms 13876 KB Output is correct
19 Correct 30 ms 14008 KB Output is correct
20 Correct 32 ms 13964 KB Output is correct
21 Correct 30 ms 13952 KB Output is correct
22 Correct 30 ms 13948 KB Output is correct
23 Correct 25 ms 11612 KB Output is correct
24 Correct 25 ms 11500 KB Output is correct
25 Correct 27 ms 11940 KB Output is correct
26 Correct 25 ms 11912 KB Output is correct
27 Correct 28 ms 12776 KB Output is correct
28 Correct 28 ms 12800 KB Output is correct
29 Correct 32 ms 12832 KB Output is correct
30 Correct 27 ms 12840 KB Output is correct
31 Correct 25 ms 11568 KB Output is correct
32 Correct 25 ms 11500 KB Output is correct
33 Correct 25 ms 12000 KB Output is correct
34 Correct 26 ms 11984 KB Output is correct
35 Correct 28 ms 12708 KB Output is correct
36 Correct 37 ms 12708 KB Output is correct
37 Correct 32 ms 12696 KB Output is correct
38 Correct 27 ms 12788 KB Output is correct
39 Correct 27 ms 12744 KB Output is correct
40 Correct 28 ms 12724 KB Output is correct
41 Correct 30 ms 13244 KB Output is correct
42 Correct 33 ms 13336 KB Output is correct
43 Correct 30 ms 13364 KB Output is correct
44 Correct 31 ms 13344 KB Output is correct
45 Correct 34 ms 13556 KB Output is correct
46 Correct 30 ms 13288 KB Output is correct
47 Correct 28 ms 12532 KB Output is correct
48 Correct 28 ms 12436 KB Output is correct
49 Correct 27 ms 12280 KB Output is correct
50 Correct 29 ms 12500 KB Output is correct
51 Correct 25 ms 11500 KB Output is correct
52 Correct 25 ms 11508 KB Output is correct
53 Correct 26 ms 11440 KB Output is correct
54 Correct 27 ms 11444 KB Output is correct
55 Correct 25 ms 11504 KB Output is correct
56 Correct 26 ms 11512 KB Output is correct
57 Correct 25 ms 11592 KB Output is correct
58 Correct 25 ms 11576 KB Output is correct
59 Correct 27 ms 11664 KB Output is correct
60 Correct 27 ms 11584 KB Output is correct