oj.uz

Submission #260870

# Submission time Handle Problem Language Result Execution time Memory
260870 2020-08-11T06:21:32 Z 문홍윤(#5067) Stray Cat (JOI20_stray) C++17
15 / 100
 69 ms 17496 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){
            prv=opp;
            return prv;
        }
        return -1;
    }
}

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 59 ms 16240 KB Output is correct
2 Correct 1 ms 1536 KB Output is correct
3 Correct 45 ms 15648 KB Output is correct
4 Correct 67 ms 17240 KB Output is correct
5 Correct 64 ms 17496 KB Output is correct
6 Correct 49 ms 15988 KB Output is correct
7 Correct 49 ms 15984 KB Output is correct
8 Correct 62 ms 16908 KB Output is correct
9 Correct 59 ms 16940 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 16240 KB Output is correct
2 Correct 1 ms 1536 KB Output is correct
3 Correct 45 ms 15648 KB Output is correct
4 Correct 67 ms 17240 KB Output is correct
5 Correct 64 ms 17496 KB Output is correct
6 Correct 49 ms 15988 KB Output is correct
7 Correct 49 ms 15984 KB Output is correct
8 Correct 62 ms 16908 KB Output is correct
9 Correct 59 ms 16940 KB Output is correct
10 Correct 46 ms 14184 KB Output is correct
11 Correct 46 ms 14144 KB Output is correct
12 Correct 45 ms 14232 KB Output is correct
13 Correct 49 ms 14216 KB Output is correct
14 Correct 46 ms 14404 KB Output is correct
15 Correct 55 ms 14884 KB Output is correct
16 Correct 66 ms 16980 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 13804 KB Output is correct
2 Correct 1 ms 1536 KB Output is correct
3 Correct 39 ms 13240 KB Output is correct
4 Correct 64 ms 14924 KB Output is correct
5 Correct 61 ms 15044 KB Output is correct
6 Correct 47 ms 13800 KB Output is correct
7 Correct 46 ms 13780 KB Output is correct
8 Correct 57 ms 14548 KB Output is correct
9 Correct 59 ms 14612 KB Output is correct
10 Correct 55 ms 14352 KB Output is correct
11 Correct 55 ms 14356 KB Output is correct
12 Correct 55 ms 14164 KB Output is correct
13 Correct 55 ms 14356 KB Output is correct
14 Correct 61 ms 14604 KB Output is correct
15 Correct 56 ms 14420 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 13804 KB Output is correct
2 Correct 1 ms 1536 KB Output is correct
3 Correct 39 ms 13240 KB Output is correct
4 Correct 64 ms 14924 KB Output is correct
5 Correct 61 ms 15044 KB Output is correct
6 Correct 47 ms 13800 KB Output is correct
7 Correct 46 ms 13780 KB Output is correct
8 Correct 57 ms 14548 KB Output is correct
9 Correct 59 ms 14612 KB Output is correct
10 Correct 55 ms 14352 KB Output is correct
11 Correct 55 ms 14356 KB Output is correct
12 Correct 55 ms 14164 KB Output is correct
13 Correct 55 ms 14356 KB Output is correct
14 Correct 61 ms 14604 KB Output is correct
15 Correct 56 ms 14420 KB Output is correct
16 Correct 41 ms 12396 KB Output is correct
17 Correct 41 ms 12292 KB Output is correct
18 Correct 45 ms 12328 KB Output is correct
19 Correct 49 ms 12236 KB Output is correct
20 Correct 52 ms 12960 KB Output is correct
21 Correct 48 ms 12716 KB Output is correct
22 Correct 57 ms 14540 KB Output is correct
23 Correct 46 ms 12464 KB Output is correct
24 Correct 44 ms 12364 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1792 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 Incorrect 2 ms 1792 KB Wrong Answer [5]
7 Halted 0 ms 0 KB -

Subtask #6
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 11860 KB Output is correct
2 Correct 49 ms 13320 KB Output is correct
3 Correct 1 ms 1600 KB Output is correct
4 Correct 40 ms 11560 KB Output is correct
5 Correct 64 ms 14224 KB Output is correct
6 Correct 67 ms 14204 KB Output is correct
7 Incorrect 44 ms 13428 KB Wrong Answer [6]
8 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 11856 KB Output is correct
2 Correct 48 ms 12748 KB Output is correct
3 Correct 1 ms 1536 KB Output is correct
4 Correct 37 ms 11572 KB Output is correct
5 Correct 69 ms 14228 KB Output is correct
6 Correct 56 ms 14408 KB Output is correct
7 Incorrect 42 ms 13396 KB Wrong Answer [6]
8 Halted 0 ms 0 KB -