oj.uz

Submission #260873

# Submission time Handle Problem Language Result Execution time Memory
260873 2020-08-11T06:30:37 Z 문홍윤(#5067) Stray Cat (JOI20_stray) C++17
15 / 100
 75 ms 16968 KB 
#include "Anthony.h"
#include <bits/stdc++.h>
#define eb emplace_back
#define mp make_pair
#define F first
#define S second
using namespace std;
typedef pair<int, int> pii;
static const int INF=1e9;

static int n, m, col[20010];
static vector<pii> link[20010];

static int que[20010], fr, re, d[20010];
static void col_typeA(){
    que[++re]=0;
    d[0]=1;
    for(fr=1; fr<=re; fr++){
        for(auto i:link[que[fr]]){
            if(d[i.F])continue;
            d[i.F]=d[que[fr]]+1;
            que[++re]=i.F;
        }
    }
    for(int i=0; i<n; i++){
        for(auto j:link[i]){
            int tmp=min(d[i], d[j.F]);
            col[j.S]=tmp%3+1;
        }
    }
}
static int rpt[6]={0, 1, 0, 0, 1, 1};
static void dfs(int num, int par, int uc){
    int tmp=link[num].size();
    if(!num)tmp++;
    int nxt=1-rpt[uc];
    if(tmp==2)nxt=(uc+1)%6;
    for(auto i:link[num]){
        if(i.F==par)continue;
        col[i.S]=rpt[nxt];
        dfs(i.F, num, nxt);
    }
}
static void col_typeB(){dfs(0, -1, 0);}

vector<int> Mark(int N, int M, int A, int B, vector<int> U, vector<int> V){
    n=N, m=M;
    vector<int> ret(m);
    for(int i=0; i<m; i++){
        link[U[i]].eb(V[i], i);
        link[V[i]].eb(U[i], i);
    }
    if(A>=3)col_typeA();
    else col_typeB();
    for(int i=0; i<m; i++)ret[i]=col[i]-(A>=3);
    return ret;
}

#include "Catherine.h"
#include <bits/stdc++.h>
#define eb emplace_back
#define mp make_pair
#define F first
#define S second
using namespace std;
typedef pair<int, int> pii;

static int typ;
void Init(int A, int B){
    if(A>=3)typ=1;
    else typ=2;
}

static int move_typeA(vector<int> vc){
    for(int i=0; i<3; i++)if(vc[i]&&!vc[(i+2)%3])return i;
}

static int rpt[6]={0, 1, 0, 0, 1, 1};
static bool fnd;
static int cnt, prv=-1, mask;
static int move_typeB(vector<int> vc){
    cnt++;
    int deg=vc[0]+vc[1];
    if(prv>=0)deg++;
    if(fnd){
        if(deg>=3){
            prv=1-prv;
            return prv;
        }
        if(vc[0])prv=0;
        else prv=1;
        return prv;
    }
    if(deg==1){
        fnd=true;
        if(cnt>1)return -1;
        if(vc[0])prv=0;
        else prv=1;
        return prv;
    }
    if(deg>=3){
        if(cnt>1)vc[prv]++;
        fnd=true;
        int tmp;
        if(vc[0]==1)tmp=0;
        else tmp=1;
        if(tmp==prv&&cnt>1)return -1;
        prv=tmp;
        return tmp;
    }
    if(cnt<=3){
        if(vc[0])prv=0;
        else prv=1;
        if(cnt==1)mask*=2, mask+=1-prv;
        mask*=2, mask+=prv;
        return prv;
    }
    if(cnt==4){
        fnd=true;
        int opp;
        if(vc[0])opp=0;
        else opp=1;
        mask*=2, mask+=opp;
        if(mask==6||mask==13||mask==26||mask==20||mask==9||mask==19){
            return -1;
        }
        prv=opp;
        return prv;
    }
}

int Move(vector<int> y){
    if(typ==1)return move_typeA(y);
    return move_typeB(y);
}

Compilation message

Catherine.cpp: In function 'int move_typeA(std::vector<int>)':
Catherine.cpp:18:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
Catherine.cpp: In function 'int move_typeB(std::vector<int>)':
Catherine.cpp:72:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
Catherine.cpp: At global scope:
Catherine.cpp:20:12: warning: 'rpt' defined but not used [-Wunused-variable]
 static int rpt[6]={0, 1, 0, 0, 1, 1};
            ^~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 16116 KB Output is correct
2 Correct 2 ms 1536 KB Output is correct
3 Correct 43 ms 14968 KB Output is correct
4 Correct 75 ms 16752 KB Output is correct
5 Correct 72 ms 16968 KB Output is correct
6 Correct 49 ms 15712 KB Output is correct
7 Correct 53 ms 15604 KB Output is correct
8 Correct 59 ms 16300 KB Output is correct
9 Correct 59 ms 16244 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 16116 KB Output is correct
2 Correct 2 ms 1536 KB Output is correct
3 Correct 43 ms 14968 KB Output is correct
4 Correct 75 ms 16752 KB Output is correct
5 Correct 72 ms 16968 KB Output is correct
6 Correct 49 ms 15712 KB Output is correct
7 Correct 53 ms 15604 KB Output is correct
8 Correct 59 ms 16300 KB Output is correct
9 Correct 59 ms 16244 KB Output is correct
10 Correct 46 ms 13744 KB Output is correct
11 Correct 45 ms 13740 KB Output is correct
12 Correct 45 ms 13724 KB Output is correct
13 Correct 46 ms 13848 KB Output is correct
14 Correct 46 ms 13988 KB Output is correct
15 Correct 53 ms 14252 KB Output is correct
16 Correct 55 ms 16472 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 13540 KB Output is correct
2 Correct 1 ms 1536 KB Output is correct
3 Correct 39 ms 12796 KB Output is correct
4 Correct 59 ms 14796 KB Output is correct
5 Correct 61 ms 14796 KB Output is correct
6 Correct 46 ms 13308 KB Output is correct
7 Correct 46 ms 13540 KB Output is correct
8 Correct 54 ms 14096 KB Output is correct
9 Correct 62 ms 14040 KB Output is correct
10 Correct 61 ms 13852 KB Output is correct
11 Correct 54 ms 13852 KB Output is correct
12 Correct 55 ms 13840 KB Output is correct
13 Correct 55 ms 13856 KB Output is correct
14 Correct 62 ms 14196 KB Output is correct
15 Correct 58 ms 14248 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 13540 KB Output is correct
2 Correct 1 ms 1536 KB Output is correct
3 Correct 39 ms 12796 KB Output is correct
4 Correct 59 ms 14796 KB Output is correct
5 Correct 61 ms 14796 KB Output is correct
6 Correct 46 ms 13308 KB Output is correct
7 Correct 46 ms 13540 KB Output is correct
8 Correct 54 ms 14096 KB Output is correct
9 Correct 62 ms 14040 KB Output is correct
10 Correct 61 ms 13852 KB Output is correct
11 Correct 54 ms 13852 KB Output is correct
12 Correct 55 ms 13840 KB Output is correct
13 Correct 55 ms 13856 KB Output is correct
14 Correct 62 ms 14196 KB Output is correct
15 Correct 58 ms 14248 KB Output is correct
16 Correct 45 ms 11896 KB Output is correct
17 Correct 45 ms 11768 KB Output is correct
18 Correct 44 ms 11768 KB Output is correct
19 Correct 44 ms 12000 KB Output is correct
20 Correct 53 ms 12596 KB Output is correct
21 Correct 48 ms 12460 KB Output is correct
22 Correct 54 ms 14424 KB Output is correct
23 Correct 44 ms 11956 KB Output is correct
24 Correct 47 ms 11948 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1856 KB Output is correct
2 Correct 1 ms 1536 KB Output is correct
3 Correct 2 ms 1536 KB Output is correct
4 Correct 2 ms 1792 KB Output is correct
5 Correct 2 ms 1792 KB Output is correct
6 Correct 2 ms 1792 KB Output is correct
7 Correct 2 ms 1792 KB Output is correct
8 Correct 2 ms 1792 KB Output is correct
9 Correct 2 ms 1792 KB Output is correct
10 Incorrect 2 ms 1792 KB Wrong Answer [5]
11 Halted 0 ms 0 KB -

Subtask #6
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 11604 KB Output is correct
2 Correct 50 ms 12412 KB Output is correct
3 Correct 1 ms 1536 KB Output is correct
4 Correct 39 ms 11248 KB Output is correct
5 Correct 60 ms 13704 KB Output is correct
6 Incorrect 41 ms 12796 KB Wrong Answer [5]
7 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 11744 KB Output is correct
2 Correct 46 ms 12340 KB Output is correct
3 Correct 1 ms 1536 KB Output is correct
4 Correct 38 ms 11128 KB Output is correct
5 Correct 58 ms 13836 KB Output is correct
6 Correct 57 ms 13704 KB Output is correct
7 Correct 46 ms 12796 KB Output is correct
8 Incorrect 43 ms 13268 KB Wrong Answer [6]
9 Halted 0 ms 0 KB -