oj.uz

답안 #947480

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
947480 2024-03-16T09:14:03 Z phoenix0423 길고양이 (JOI20_stray) C++17
15 / 100
 45 ms 16516 KB 
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> pll;
#define pb push_back
#define eb emplace_back
const int INF = 1e9;
#include "Anthony.h"

vector<int> Mark(int n, int m, int a, int b, vector<int> u, vector<int> v){
    vector<vector<pll>> adj(n);
    vector<int> dist(n, INF), deg(n);
    dist[0] = 0;
    for(int i = 0; i < m; i++){
        adj[u[i]].eb(v[i], i);
        adj[v[i]].eb(u[i], i);
        deg[u[i]] ++, deg[v[i]] ++;
    }
    vector<int> color(m, -1);
    vector<int> bd(n);
    bd[0] = 0;
    queue<pll> q;
    q.push({0, 0});
    if(a >= 3){
        while(!q.empty()){
            auto [pos, lst] = q.front(); q.pop();
            for(auto [x, id] : adj[pos]){
                if(color[id] != -1) continue;
                if(dist[x] != INF){
                  if(dist[x] >= dist[pos]) color[id] = (lst + 1) % a;
                  else color[id] = lst;
                  continue;
                }
                // cout<<"do : "<<pos<<" "<<x<<" "<<lst<<"\n";
                dist[x] = dist[pos] + 1;
                color[id] = (lst + 1) % a;
                q.push({x, color[id]});
            }
        }
        // cout<<"dist : ";
        // for(auto x : dist) cout<<x<<" ";
        // cout<<"\n";
    }
    else{
        string ck = "121221";
        while(!q.empty()){
            auto [pos, lst] = q.front(); q.pop();
            int put;
            if(deg[pos] > 2){
                if(ck[lst] == '1') put = 1;
                else put = 0;
            }
            else put = (lst + 1) % 6;
            for(auto [x, id] : adj[pos]){
                if(dist[x] != INF) continue;
                dist[x] = dist[pos] + 1;
                color[id] = (ck[put] - '1');
                q.push({x, put});
            }
        }
    }
    return color;
}

// signed main(void){
//     int n, m, a, b, s;
//     cin>>n>>m>>a>>b>>s;
//     vector<int> u(m), v(m);
//     for(int i = 0; i < m; i++) cin>>u[i]>>v[i];
//     auto c = Mark(n, m, a, b, u, v);
//     for(auto x : c) cout<<x<<" ";
//     cout<<"\n";
// }
#include "Catherine.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;

int A, B, lst = -1, ok = 0, bk = 0;
int fir = 0;
string ck = "";
string s = "010110010110";

void Init(int a, int b){
    A = a, B = b;
}

int find_dir(){
  for(int i = 0; i < 6; i++){
    int dif = 0;
    for(int j = 0; j < 5; j++) if(ck[j] != s[i + j]){
      dif = 1;
      break;
    }
    if(!dif) return 1;
  }
  return 0;
}
int Move(vector<int> y){
  // cout<<"ck : "<<A<<" "<<B<<"\n";
  if(lst != -1) y[lst]++;
  int deg = 0;
  for(auto x : y) deg += (x != 0);
  if(A >= 3){
      if(deg == 1){
          return max_element(y.begin(), y.end()) - y.begin();
      }
      for(int i = 0; i < A; i++){
          // cout<<"try : "<<i<<" "<<y[i]<<" "<<y[(i + 1) % A]<<"\n";
          if(y[i] && y[(i + 1) % A]){
              return i;
          }
      }
  }
  // a = 2
  deg = accumulate(y.begin(), y.end(), 0);
  // cout<<"deg : "<<deg<<"\n";
  if(deg == 1){
    // cout<<"nothing, back\n";
    ok = 1;
    if(lst == -1){
      lst = y[0] == 0;
      return lst;
    }
    else return -1;
  }
  if(deg > 2){
      ok = 1;
      if(y[0] == 1){
        int tmp = lst;
        lst = 0;
        if(tmp == 0) return -1;
        return 0;
      }
      else{
        int tmp = lst;
        lst = 1;
        if(tmp == 1) return -1;
        else return 1;
      }
  }
  // deg = 2
  if(ok){
    y[lst]--;
    if(y[0]){
      lst = 0;
      return 0;
    }
    lst = 1;
    return 1;
  }
  auto rot = [&]() -> int{
    int d = find_dir();
    // cout<<"end, change dir : "<<d<<"\n";
    ok = 1;
    if(d){
      return -1;
    }
    y[lst] --;
    if(y[0]){
      lst = 0;
      return 0;
    }
    else{
      lst = 1;
      return 1;
    }
  };
  if(lst == -1){
    if(y[0] == 2){
      ck += "00", lst = 0;
      return 0;
    }
    else if(y[1] == 2){
      ck += "11", lst = 1;
      return 1;
    }
    else{
      ck += "01", lst = 1;
      return 1;
    }
  }
  else{
    y[lst] --;
    if(y[0]){
      ck += '0';
      if(ck.size() == 5) return rot();
      lst = 0;
      return 0;
    }
    else{
      ck += '1';
      if(ck.size() == 5) return rot();
      lst = 1;
      return 1;
    }
  }
}
/*
16 15 2 6 11
0 1
1 2
2 3
3 4
4 8
2 5 
5 6
6 7
7 9
6 10
10 11
11 12
12 13
13 14
13 15
*/

Subtask #1
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 15364 KB Output is correct
2 Correct 1 ms 792 KB Output is correct
3 Correct 23 ms 14984 KB Output is correct
4 Correct 36 ms 16404 KB Output is correct
5 Correct 36 ms 16516 KB Output is correct
6 Correct 26 ms 15200 KB Output is correct
7 Correct 28 ms 15228 KB Output is correct
8 Correct 35 ms 16048 KB Output is correct
9 Correct 33 ms 15992 KB Output is correct

Subtask #2
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 15364 KB Output is correct
2 Correct 1 ms 792 KB Output is correct
3 Correct 23 ms 14984 KB Output is correct
4 Correct 36 ms 16404 KB Output is correct
5 Correct 36 ms 16516 KB Output is correct
6 Correct 26 ms 15200 KB Output is correct
7 Correct 28 ms 15228 KB Output is correct
8 Correct 35 ms 16048 KB Output is correct
9 Correct 33 ms 15992 KB Output is correct
10 Correct 28 ms 13436 KB Output is correct
11 Correct 27 ms 13436 KB Output is correct
12 Correct 28 ms 13188 KB Output is correct
13 Correct 27 ms 13296 KB Output is correct
14 Correct 27 ms 13692 KB Output is correct
15 Correct 30 ms 13884 KB Output is correct
16 Correct 30 ms 16036 KB Output is correct

Subtask #3
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 12912 KB Output is correct
2 Correct 0 ms 792 KB Output is correct
3 Correct 24 ms 12676 KB Output is correct
4 Correct 37 ms 14456 KB Output is correct
5 Correct 31 ms 14468 KB Output is correct
6 Correct 27 ms 12964 KB Output is correct
7 Correct 28 ms 12976 KB Output is correct
8 Correct 31 ms 13692 KB Output is correct
9 Correct 30 ms 13700 KB Output is correct
10 Correct 27 ms 13420 KB Output is correct
11 Correct 32 ms 13236 KB Output is correct
12 Correct 27 ms 13436 KB Output is correct
13 Correct 37 ms 13328 KB Output is correct
14 Correct 34 ms 13756 KB Output is correct
15 Correct 32 ms 13768 KB Output is correct

Subtask #4
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 12912 KB Output is correct
2 Correct 0 ms 792 KB Output is correct
3 Correct 24 ms 12676 KB Output is correct
4 Correct 37 ms 14456 KB Output is correct
5 Correct 31 ms 14468 KB Output is correct
6 Correct 27 ms 12964 KB Output is correct
7 Correct 28 ms 12976 KB Output is correct
8 Correct 31 ms 13692 KB Output is correct
9 Correct 30 ms 13700 KB Output is correct
10 Correct 27 ms 13420 KB Output is correct
11 Correct 32 ms 13236 KB Output is correct
12 Correct 27 ms 13436 KB Output is correct
13 Correct 37 ms 13328 KB Output is correct
14 Correct 34 ms 13756 KB Output is correct
15 Correct 32 ms 13768 KB Output is correct
16 Correct 24 ms 11384 KB Output is correct
17 Correct 24 ms 11640 KB Output is correct
18 Correct 25 ms 11248 KB Output is correct
19 Correct 24 ms 11244 KB Output is correct
20 Correct 26 ms 12004 KB Output is correct
21 Correct 26 ms 11760 KB Output is correct
22 Correct 28 ms 13936 KB Output is correct
23 Correct 27 ms 11492 KB Output is correct
24 Correct 25 ms 11512 KB Output is correct

Subtask #5
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1032 KB Output is correct
2 Correct 0 ms 792 KB Output is correct
3 Correct 1 ms 1036 KB Output is correct
4 Correct 2 ms 1044 KB Output is correct
5 Correct 2 ms 1044 KB Output is correct
6 Correct 2 ms 1052 KB Output is correct
7 Correct 2 ms 1044 KB Output is correct
8 Incorrect 0 ms 1052 KB Wrong Answer [5]
9 Halted 0 ms 0 KB -

Subtask #6
0 / 71.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 11196 KB Output is correct
2 Correct 31 ms 11644 KB Output is correct
3 Correct 0 ms 792 KB Output is correct
4 Correct 27 ms 11076 KB Output is correct
5 Correct 32 ms 12356 KB Output is correct
6 Incorrect 24 ms 11324 KB Wrong Answer [5]
7 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 11064 KB Output is correct
2 Correct 26 ms 11644 KB Output is correct
3 Correct 1 ms 792 KB Output is correct
4 Correct 28 ms 11228 KB Output is correct
5 Correct 45 ms 12412 KB Output is correct
6 Incorrect 24 ms 11448 KB Wrong Answer [5]
7 Halted 0 ms 0 KB -