oj.uz

답안 #710447

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
710447 2023-03-15T08:46:41 Z zyq_ 길고양이 (JOI20_stray) C++17
0 / 100
 37 ms 20304 KB 
#include <bits/stdc++.h>
using namespace std;

vector<pair<int, int> > adjList[200010];
int lonecnt[200010];
int ans[200010];

int lonecolour[] = {0, 1, 1, 0, 0, 1};

void dfs(int x, int dist, int parent = -1){ //ret val is lone seg count
    for(auto it: adjList[x]){
        if(it.first == parent) continue;
        if((x==0 && (int)adjList[x].size()==1)||(x!=0&&(int)adjList[x].size()==2)){
            if(lonecnt[x] != 0){
                lonecnt[it.first] = lonecnt[x]+1;
            }
            else{
                if(dist % 2 == 0){
                    lonecnt[it.first] = 1;
                }
                else{
                    lonecnt[it.first] = 0;
                }
            }
        }
        dfs(it.first, dist+1, x);
    }
}
//weve got the lonecnt time to colour some stuff

void colouring(int x, int prev, int parent = -1){
    for(auto it: adjList[x]){
        if(it.first == parent) continue;
        //start to colour from 0
        if(lonecnt[it.first] == 0){
            ans[it.second] = (prev+1)%2;
        }
        else{
            ans[it.second] = lonecolour[(lonecnt[it.first]-1)%6];
        }
        colouring(it.first, ans[it.second], x);
    }
}

vector<int> Mark(int N, int M, int A, int B, vector<int> U, vector<int> V){
    //look for lone segments
    for(int a=0; a<M; a++){
        adjList[U[a]].push_back({V[a], a});
        adjList[V[a]].push_back({U[a], a});
    }
    dfs(0, 0);
    colouring(0, 1);
    vector<int> ret;
    for(int a=0; a<M; a++) ret.push_back(ans[a]);
    return ret;
}
#include <bits/stdc++.h>
using namespace std;

bool resolved;
int prev1, prev2, prev3, prev4, prev5, prev6;

void Init(int A, int B){
    resolved = false;
    prev1 = prev2 = prev3 = prev4 = prev5 = prev6 = -1;
}

int Move(vector<int> y){
    //check LOL
    if(resolved){
        //keep moving in different
        if(prev1 == 0){
            prev1 = 1;
            return 1;
        }
        else{
            prev1 = 0;
            return 0;
        }
    }
    else{
        //check if current place is good ?
        if(prev1 == -1){
            //first step
            if(y[1] >= 1){
                prev1 = 1;
                return 1;
            }
            else{
                prev1 = 0;
                return 0;
            }
        }
        if(y[0] + y[1] == 1){
            resolved = true;
            if(y[0] == 1) prev1 = 0;
            else prev1 = 1;
            return -1;
        }
        if(y[0] + y[1] > 2){
            if(y[0] == 1){
                resolved = true;
                prev1 = 0;
                return -1;
            }
            else{
                resolved = true;
                prev1 = 1;
                return -1;
            }
        }
        //now is when on lone
        //start moving
        else{
            //not first step
            if(/*leaf node*/ y[1] + y[0] == 1) return -1;
            prev6 = prev5;
            prev5 = prev4;
            prev4 = prev3;
            prev3 = prev2;
            prev2 = prev1;
            //look at prev2
            if(y[0] == 2){
                prev1 = 0;
            }
            else if(y[1] == 2){
                prev1 = 1;
            }
            else{
                if(prev2 == 1){
                    prev1 = 0;
                }
                else{
                    prev1 = 1;
                }
            }
            if(prev1 != prev2 && prev3 == prev4 && prev3 != -1){
                resolved = true;
                if(prev3 == 0){
                    //rightdirectoin
                    return prev1;
                }
                else{
                    return -1;
                }
            }
            else{
                return prev1;
            }
        }
    }
}

Subtask #1
0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 35 ms 20304 KB Wrong Answer [5]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 35 ms 20304 KB Wrong Answer [5]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 37 ms 18160 KB Wrong Answer [5]
2 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 37 ms 18160 KB Wrong Answer [5]
2 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 5516 KB Wrong Answer [5]
2 Halted 0 ms 0 KB -

Subtask #6
0 / 71.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 32 ms 15540 KB Wrong Answer [5]
2 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 15736 KB Output is correct
2 Incorrect 35 ms 16636 KB Wrong Answer [5]
3 Halted 0 ms 0 KB -