oj.uz

Submission #260874

# Submission time Handle Problem Language Result Execution time Memory
260874 2020-08-11T06:31:41 Z 문홍윤(#5067) Stray Cat (JOI20_stray) C++17
15 / 100
 66 ms 17032 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:70: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 54 ms 15868 KB Output is correct
2 Correct 1 ms 1536 KB Output is correct
3 Correct 40 ms 15124 KB Output is correct
4 Correct 65 ms 16876 KB Output is correct
5 Correct 65 ms 17032 KB Output is correct
6 Correct 49 ms 15736 KB Output is correct
7 Correct 52 ms 15720 KB Output is correct
8 Correct 58 ms 16268 KB Output is correct
9 Correct 65 ms 16244 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 15868 KB Output is correct
2 Correct 1 ms 1536 KB Output is correct
3 Correct 40 ms 15124 KB Output is correct
4 Correct 65 ms 16876 KB Output is correct
5 Correct 65 ms 17032 KB Output is correct
6 Correct 49 ms 15736 KB Output is correct
7 Correct 52 ms 15720 KB Output is correct
8 Correct 58 ms 16268 KB Output is correct
9 Correct 65 ms 16244 KB Output is correct
10 Correct 45 ms 13560 KB Output is correct
11 Correct 45 ms 13688 KB Output is correct
12 Correct 46 ms 13724 KB Output is correct
13 Correct 45 ms 13732 KB Output is correct
14 Correct 48 ms 13816 KB Output is correct
15 Correct 54 ms 14368 KB Output is correct
16 Correct 56 ms 16380 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 13552 KB Output is correct
2 Correct 1 ms 1536 KB Output is correct
3 Correct 40 ms 12972 KB Output is correct
4 Correct 63 ms 14800 KB Output is correct
5 Correct 63 ms 14800 KB Output is correct
6 Correct 47 ms 13540 KB Output is correct
7 Correct 49 ms 13540 KB Output is correct
8 Correct 55 ms 13980 KB Output is correct
9 Correct 56 ms 14092 KB Output is correct
10 Correct 50 ms 13820 KB Output is correct
11 Correct 51 ms 13836 KB Output is correct
12 Correct 52 ms 13848 KB Output is correct
13 Correct 53 ms 13836 KB Output is correct
14 Correct 55 ms 14092 KB Output is correct
15 Correct 56 ms 14092 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 13552 KB Output is correct
2 Correct 1 ms 1536 KB Output is correct
3 Correct 40 ms 12972 KB Output is correct
4 Correct 63 ms 14800 KB Output is correct
5 Correct 63 ms 14800 KB Output is correct
6 Correct 47 ms 13540 KB Output is correct
7 Correct 49 ms 13540 KB Output is correct
8 Correct 55 ms 13980 KB Output is correct
9 Correct 56 ms 14092 KB Output is correct
10 Correct 50 ms 13820 KB Output is correct
11 Correct 51 ms 13836 KB Output is correct
12 Correct 52 ms 13848 KB Output is correct
13 Correct 53 ms 13836 KB Output is correct
14 Correct 55 ms 14092 KB Output is correct
15 Correct 56 ms 14092 KB Output is correct
16 Correct 40 ms 11672 KB Output is correct
17 Correct 41 ms 11776 KB Output is correct
18 Correct 53 ms 11760 KB Output is correct
19 Correct 53 ms 11944 KB Output is correct
20 Correct 53 ms 12392 KB Output is correct
21 Correct 49 ms 12332 KB Output is correct
22 Correct 54 ms 14428 KB Output is correct
23 Correct 55 ms 11960 KB Output is correct
24 Correct 45 ms 12008 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1536 KB Output is correct
2 Correct 1 ms 1536 KB Output is correct
3 Correct 2 ms 1792 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 2048 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 54 ms 11608 KB Output is correct
2 Correct 55 ms 12540 KB Output is correct
3 Correct 2 ms 1536 KB Output is correct
4 Correct 38 ms 11328 KB Output is correct
5 Correct 60 ms 13684 KB Output is correct
6 Incorrect 43 ms 12812 KB Wrong Answer [5]
7 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 11628 KB Output is correct
2 Correct 56 ms 12460 KB Output is correct
3 Correct 2 ms 1536 KB Output is correct
4 Correct 40 ms 11308 KB Output is correct
5 Correct 58 ms 13828 KB Output is correct
6 Correct 66 ms 13720 KB Output is correct
7 Correct 46 ms 13016 KB Output is correct
8 Incorrect 46 ms 12928 KB Wrong Answer [6]
9 Halted 0 ms 0 KB -