답안 #997035

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
997035	2024-06-11T15:51:00 Z	TimDee	길고양이 (JOI20_stray)	C++17	100 / 100	36 ms	16752 KB

#include "Anthony.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0; i<(n); ++i)
#define pb push_back
#define pi pair<int,int>
#define f first
#define s second 

const int N=2e4+4;
vector<pi> adj[N];
int z[N];
int c[N];
int ed[N];

vector<int> ptrn={0,1,1,0,0,1};

void dfs(int u, int p) {
    for(auto&e:adj[u]) {
        int v=e.f, i=e.s;
        if (v==p) continue;
        if (adj[v].size()==2) {
            z[v]=z[u]+1;
            c[v]=ptrn[z[u]%6];
            ed[i]=ptrn[z[u]%6];
        } else {
            z[v]=c[u];
            c[v]=c[u]^1;
            ed[i]=c[u]^1;
        }
        dfs(v,u);
    }
}

vector<int> Mark(int n, int m, int A, int B, vector<int> u, vector<int> v) {
     
    if (!B) {
        forn(i,m) adj[u[i]].pb({v[i],i}), adj[v[i]].pb({u[i],i});
        queue<int> q; q.push(0);
        vector<int> vis(n); vis[0]=1;
        vector<int> d(n);
        while (q.size()) {
            int u=q.front(); q.pop();
            for(auto&e:adj[u]) {
                int v=e.f, i=e.s;
                if (!z[i]) {
                    z[i] = (d[u]%3)+1;
                }
                if (vis[v]) continue;
                vis[v]=1;
                q.push(v);
                d[v]=d[u]+1;
            }
        }
        vector<int> ans(m);
        forn(i,m) ans[i]=z[i]-1;
        return ans;
    }
    forn(i,m) adj[u[i]].pb({v[i],i}), adj[v[i]].pb({u[i],i});
    z[0]=1; dfs(0,-1);
    vector<int> ans(m);
    forn(i,m) ans[i]=ed[i];
    return ans;

}

#include "Catherine.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0; i<(n); ++i)
#define pb push_back
#define pi pair<int,int>
#define f first
#define s second 

int fmove=1;
int rdir=0;
int last=-1;
int alt=0;
void Init(int A, int B) {
    if (!B) alt=1;
}

vector<int> ok;
vector<int> ptn={0,1,1,0,0,1};

int Move(vector<int> a) {
    
    if (alt) {
        if (a[0]&&a[2]) return 2;
        if (a[0]&&a[1]) return 0;
        if (a[1]&&a[2]) return 1;
        forn(i,3) if (a[i]) return i;
    }

    if (fmove) {
        fmove=0;
        if (a[0]+a[1] == 1) {
            rdir=1;
            if (a[0]) return last=0;
            if (a[1]) return last=1;
            assert(0);
        }
        if (a[0]+a[1]>2) {
            rdir=1;
            if (a[0]==1) return last=0;
            if (a[1]==1) return last=1;
            assert(0);
        }
        for(int i=1; i>=0; --i) forn(j,a[i]) ok.pb(i);
        forn(i,2) if (a[i]) return last=i;
        assert(0);
    }

    if (rdir) {
        if (!(a[0]+a[1])) return -1;
        assert(a[0]+a[1]);
        if (a[0]+a[1]==1) forn(i,2) if (a[i]) return last=i;
        assert(a[last^1]);
        return last^=1;
    }
    
    if (a[0]+a[1]==0) {
        rdir = 1;
        return -1;
    }
    if (a[0]+a[1] > 1) {
        if (a[0] && a[1]) {
            rdir=1;
            return last^=1;
        }
        rdir=1;
        return -1;
    }

    if (a[0]) {
        ok.pb(0);
    } else {
        ok.pb(1);
    }

    if (ok.size()==5) {
        int kk=0;
        forn(i,6) {
            int z=1;
            forn(j,5) z&=ok[j]==ptn[(i+j)%6];
            kk|=z;
        }
        if (kk) {
            rdir=1;
            return -1;
        }
        rdir=1;
        return last=ok.back();
    }
    return last=ok.back();

}

Subtask #1
2.0 / 2.0

#	결과	실행 시간	메모리	Grader output
1	Correct	26 ms	15708 KB	Output is correct
2	Correct	0 ms	1304 KB	Output is correct
3	Correct	22 ms	15236 KB	Output is correct
4	Correct	30 ms	16752 KB	Output is correct
5	Correct	29 ms	16724 KB	Output is correct
6	Correct	27 ms	15480 KB	Output is correct
7	Correct	28 ms	15484 KB	Output is correct
8	Correct	31 ms	16200 KB	Output is correct
9	Correct	28 ms	16248 KB	Output is correct

Subtask #2
2.0 / 2.0

#	결과	실행 시간	메모리	Grader output
1	Correct	26 ms	15708 KB	Output is correct
2	Correct	0 ms	1304 KB	Output is correct
3	Correct	22 ms	15236 KB	Output is correct
4	Correct	30 ms	16752 KB	Output is correct
5	Correct	29 ms	16724 KB	Output is correct
6	Correct	27 ms	15480 KB	Output is correct
7	Correct	28 ms	15484 KB	Output is correct
8	Correct	31 ms	16200 KB	Output is correct
9	Correct	28 ms	16248 KB	Output is correct
10	Correct	25 ms	13676 KB	Output is correct
11	Correct	22 ms	13684 KB	Output is correct
12	Correct	23 ms	13680 KB	Output is correct
13	Correct	23 ms	13688 KB	Output is correct
14	Correct	24 ms	13764 KB	Output is correct
15	Correct	30 ms	14208 KB	Output is correct
16	Correct	28 ms	16300 KB	Output is correct

Subtask #3
2.0 / 2.0

#	결과	실행 시간	메모리	Grader output
1	Correct	31 ms	13108 KB	Output is correct
2	Correct	1 ms	1296 KB	Output is correct
3	Correct	20 ms	12932 KB	Output is correct
4	Correct	30 ms	14724 KB	Output is correct
5	Correct	29 ms	14716 KB	Output is correct
6	Correct	25 ms	13172 KB	Output is correct
7	Correct	25 ms	13168 KB	Output is correct
8	Correct	31 ms	13928 KB	Output is correct
9	Correct	31 ms	13852 KB	Output is correct
10	Correct	27 ms	13692 KB	Output is correct
11	Correct	26 ms	13680 KB	Output is correct
12	Correct	30 ms	13692 KB	Output is correct
13	Correct	26 ms	13556 KB	Output is correct
14	Correct	26 ms	14060 KB	Output is correct
15	Correct	30 ms	13948 KB	Output is correct

Subtask #4
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	31 ms	13108 KB	Output is correct
2	Correct	1 ms	1296 KB	Output is correct
3	Correct	20 ms	12932 KB	Output is correct
4	Correct	30 ms	14724 KB	Output is correct
5	Correct	29 ms	14716 KB	Output is correct
6	Correct	25 ms	13172 KB	Output is correct
7	Correct	25 ms	13168 KB	Output is correct
8	Correct	31 ms	13928 KB	Output is correct
9	Correct	31 ms	13852 KB	Output is correct
10	Correct	27 ms	13692 KB	Output is correct
11	Correct	26 ms	13680 KB	Output is correct
12	Correct	30 ms	13692 KB	Output is correct
13	Correct	26 ms	13556 KB	Output is correct
14	Correct	26 ms	14060 KB	Output is correct
15	Correct	30 ms	13948 KB	Output is correct
16	Correct	22 ms	11628 KB	Output is correct
17	Correct	25 ms	11644 KB	Output is correct
18	Correct	22 ms	11656 KB	Output is correct
19	Correct	24 ms	11576 KB	Output is correct
20	Correct	27 ms	12400 KB	Output is correct
21	Correct	23 ms	12064 KB	Output is correct
22	Correct	30 ms	14160 KB	Output is correct
23	Correct	25 ms	11888 KB	Output is correct
24	Correct	25 ms	11896 KB	Output is correct

Subtask #5
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	1564 KB	Output is correct
2	Correct	1 ms	1308 KB	Output is correct
3	Correct	1 ms	1568 KB	Output is correct
4	Correct	0 ms	1568 KB	Output is correct
5	Correct	1 ms	1568 KB	Output is correct
6	Correct	1 ms	1572 KB	Output is correct
7	Correct	2 ms	1568 KB	Output is correct
8	Correct	2 ms	1556 KB	Output is correct
9	Correct	1 ms	1564 KB	Output is correct
10	Correct	1 ms	1560 KB	Output is correct
11	Correct	1 ms	1564 KB	Output is correct
12	Correct	2 ms	1564 KB	Output is correct
13	Correct	1 ms	1568 KB	Output is correct
14	Correct	1 ms	1568 KB	Output is correct
15	Correct	1 ms	1560 KB	Output is correct
16	Correct	2 ms	1560 KB	Output is correct
17	Correct	1 ms	1560 KB	Output is correct
18	Correct	0 ms	1564 KB	Output is correct
19	Correct	1 ms	1568 KB	Output is correct
20	Correct	1 ms	1820 KB	Output is correct
21	Correct	1 ms	1560 KB	Output is correct
22	Correct	1 ms	1560 KB	Output is correct
23	Correct	1 ms	1568 KB	Output is correct
24	Correct	1 ms	1568 KB	Output is correct
25	Correct	2 ms	1552 KB	Output is correct
26	Correct	1 ms	1560 KB	Output is correct
27	Correct	1 ms	1568 KB	Output is correct
28	Correct	1 ms	1560 KB	Output is correct

Subtask #6
71.0 / 71.0

#	결과	실행 시간	메모리	Grader output
1	Correct	25 ms	11716 KB	Output is correct
2	Correct	28 ms	12632 KB	Output is correct
3	Correct	1 ms	1304 KB	Output is correct
4	Correct	22 ms	11388 KB	Output is correct
5	Correct	35 ms	14164 KB	Output is correct
6	Correct	32 ms	14196 KB	Output is correct
7	Correct	28 ms	13152 KB	Output is correct
8	Correct	25 ms	13640 KB	Output is correct
9	Correct	27 ms	14644 KB	Output is correct
10	Correct	33 ms	14500 KB	Output is correct
11	Correct	36 ms	14688 KB	Output is correct
12	Correct	33 ms	14668 KB	Output is correct
13	Correct	31 ms	14644 KB	Output is correct
14	Correct	27 ms	14692 KB	Output is correct
15	Correct	30 ms	14676 KB	Output is correct
16	Correct	28 ms	14684 KB	Output is correct
17	Correct	26 ms	14324 KB	Output is correct
18	Correct	34 ms	14348 KB	Output is correct
19	Correct	28 ms	14412 KB	Output is correct
20	Correct	33 ms	14416 KB	Output is correct
21	Correct	26 ms	14388 KB	Output is correct
22	Correct	26 ms	14424 KB	Output is correct
23	Correct	26 ms	11852 KB	Output is correct
24	Correct	22 ms	12016 KB	Output is correct
25	Correct	26 ms	12360 KB	Output is correct
26	Correct	27 ms	12364 KB	Output is correct
27	Correct	25 ms	13140 KB	Output is correct
28	Correct	25 ms	13136 KB	Output is correct
29	Correct	26 ms	13132 KB	Output is correct
30	Correct	30 ms	13344 KB	Output is correct
31	Correct	24 ms	11852 KB	Output is correct
32	Correct	22 ms	11864 KB	Output is correct
33	Correct	24 ms	12360 KB	Output is correct
34	Correct	24 ms	12628 KB	Output is correct
35	Correct	24 ms	13132 KB	Output is correct
36	Correct	27 ms	13104 KB	Output is correct
37	Correct	24 ms	13148 KB	Output is correct
38	Correct	25 ms	13144 KB	Output is correct
39	Correct	25 ms	13216 KB	Output is correct
40	Correct	29 ms	13092 KB	Output is correct
41	Correct	26 ms	13668 KB	Output is correct
42	Correct	26 ms	13760 KB	Output is correct
43	Correct	26 ms	13644 KB	Output is correct
44	Correct	27 ms	13656 KB	Output is correct
45	Correct	26 ms	13656 KB	Output is correct
46	Correct	30 ms	13840 KB	Output is correct
47	Correct	25 ms	13136 KB	Output is correct
48	Correct	25 ms	13140 KB	Output is correct
49	Correct	25 ms	12884 KB	Output is correct
50	Correct	24 ms	13064 KB	Output is correct
51	Correct	23 ms	12184 KB	Output is correct
52	Correct	28 ms	12176 KB	Output is correct
53	Correct	23 ms	12120 KB	Output is correct
54	Correct	22 ms	12120 KB	Output is correct
55	Correct	20 ms	12112 KB	Output is correct
56	Correct	24 ms	12116 KB	Output is correct
57	Correct	24 ms	12184 KB	Output is correct
58	Correct	20 ms	12112 KB	Output is correct
59	Correct	24 ms	12116 KB	Output is correct
60	Correct	24 ms	12124 KB	Output is correct

Subtask #7
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	22 ms	11632 KB	Output is correct
2	Correct	24 ms	12396 KB	Output is correct
3	Correct	1 ms	1308 KB	Output is correct
4	Correct	18 ms	11400 KB	Output is correct
5	Correct	27 ms	14268 KB	Output is correct
6	Correct	33 ms	14204 KB	Output is correct
7	Correct	24 ms	13184 KB	Output is correct
8	Correct	26 ms	13712 KB	Output is correct
9	Correct	33 ms	14824 KB	Output is correct
10	Correct	34 ms	14420 KB	Output is correct
11	Correct	28 ms	14680 KB	Output is correct
12	Correct	27 ms	14676 KB	Output is correct
13	Correct	27 ms	14760 KB	Output is correct
14	Correct	28 ms	14672 KB	Output is correct
15	Correct	27 ms	14676 KB	Output is correct
16	Correct	26 ms	14672 KB	Output is correct
17	Correct	33 ms	14248 KB	Output is correct
18	Correct	26 ms	14248 KB	Output is correct
19	Correct	30 ms	14208 KB	Output is correct
20	Correct	28 ms	14412 KB	Output is correct
21	Correct	33 ms	14208 KB	Output is correct
22	Correct	27 ms	14268 KB	Output is correct
23	Correct	22 ms	11844 KB	Output is correct
24	Correct	22 ms	11848 KB	Output is correct
25	Correct	25 ms	12356 KB	Output is correct
26	Correct	22 ms	12368 KB	Output is correct
27	Correct	25 ms	13136 KB	Output is correct
28	Correct	26 ms	13400 KB	Output is correct
29	Correct	24 ms	13384 KB	Output is correct
30	Correct	26 ms	13176 KB	Output is correct
31	Correct	24 ms	11860 KB	Output is correct
32	Correct	26 ms	11856 KB	Output is correct
33	Correct	28 ms	12632 KB	Output is correct
34	Correct	22 ms	12368 KB	Output is correct
35	Correct	27 ms	13148 KB	Output is correct
36	Correct	27 ms	13192 KB	Output is correct
37	Correct	27 ms	13132 KB	Output is correct
38	Correct	26 ms	13280 KB	Output is correct
39	Correct	27 ms	13140 KB	Output is correct
40	Correct	26 ms	13144 KB	Output is correct
41	Correct	32 ms	13656 KB	Output is correct
42	Correct	26 ms	13640 KB	Output is correct
43	Correct	26 ms	13712 KB	Output is correct
44	Correct	26 ms	13612 KB	Output is correct
45	Correct	26 ms	13640 KB	Output is correct
46	Correct	31 ms	13636 KB	Output is correct
47	Correct	24 ms	13116 KB	Output is correct
48	Correct	24 ms	13148 KB	Output is correct
49	Correct	24 ms	12908 KB	Output is correct
50	Correct	24 ms	13152 KB	Output is correct
51	Correct	24 ms	12108 KB	Output is correct
52	Correct	26 ms	12124 KB	Output is correct
53	Correct	29 ms	12180 KB	Output is correct
54	Correct	27 ms	12192 KB	Output is correct
55	Correct	23 ms	12128 KB	Output is correct
56	Correct	23 ms	12048 KB	Output is correct
57	Correct	24 ms	12128 KB	Output is correct
58	Correct	22 ms	12128 KB	Output is correct
59	Correct	26 ms	12120 KB	Output is correct
60	Correct	25 ms	12128 KB	Output is correct

답안 #997035

Compilation message

Subtask #1 2.0 / 2.0

Subtask #2 2.0 / 2.0

Subtask #3 2.0 / 2.0

Subtask #4 9.0 / 9.0

Subtask #5 5.0 / 5.0

Subtask #6 71.0 / 71.0

Subtask #7 9.0 / 9.0

Subtask #1
2.0 / 2.0

Subtask #2
2.0 / 2.0

Subtask #3
2.0 / 2.0

Subtask #4
9.0 / 9.0

Subtask #5
5.0 / 5.0

Subtask #6
71.0 / 71.0

Subtask #7
9.0 / 9.0