oj.uz

Submission #947492

# Submission time Handle Problem Language Result Execution time Memory
947492 2024-03-16T09:44:58 Z phoenix0423 Stray Cat (JOI20_stray) C++17
20 / 100
 37 ms 16920 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;
string ck = "";
string s = "010110010110";

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

int find_dir(){
  return 1;
  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;
        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

# Verdict Execution time Memory Grader output
1 Correct 28 ms 15928 KB Output is correct
2 Correct 0 ms 800 KB Output is correct
3 Correct 23 ms 15432 KB Output is correct
4 Correct 34 ms 16780 KB Output is correct
5 Correct 35 ms 16920 KB Output is correct
6 Correct 34 ms 15948 KB Output is correct
7 Correct 27 ms 15704 KB Output is correct
8 Correct 33 ms 16428 KB Output is correct
9 Correct 32 ms 16448 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 15928 KB Output is correct
2 Correct 0 ms 800 KB Output is correct
3 Correct 23 ms 15432 KB Output is correct
4 Correct 34 ms 16780 KB Output is correct
5 Correct 35 ms 16920 KB Output is correct
6 Correct 34 ms 15948 KB Output is correct
7 Correct 27 ms 15704 KB Output is correct
8 Correct 33 ms 16428 KB Output is correct
9 Correct 32 ms 16448 KB Output is correct
10 Correct 25 ms 13752 KB Output is correct
11 Correct 28 ms 13760 KB Output is correct
12 Correct 27 ms 13744 KB Output is correct
13 Correct 28 ms 13828 KB Output is correct
14 Correct 31 ms 13984 KB Output is correct
15 Correct 28 ms 14288 KB Output is correct
16 Correct 30 ms 16340 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 13452 KB Output is correct
2 Correct 1 ms 796 KB Output is correct
3 Correct 26 ms 12884 KB Output is correct
4 Correct 33 ms 14900 KB Output is correct
5 Correct 34 ms 14704 KB Output is correct
6 Correct 27 ms 13368 KB Output is correct
7 Correct 28 ms 13628 KB Output is correct
8 Correct 33 ms 14084 KB Output is correct
9 Correct 31 ms 14252 KB Output is correct
10 Correct 27 ms 13924 KB Output is correct
11 Correct 28 ms 13948 KB Output is correct
12 Correct 27 ms 13912 KB Output is correct
13 Correct 27 ms 13892 KB Output is correct
14 Correct 32 ms 14376 KB Output is correct
15 Correct 30 ms 14032 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 13452 KB Output is correct
2 Correct 1 ms 796 KB Output is correct
3 Correct 26 ms 12884 KB Output is correct
4 Correct 33 ms 14900 KB Output is correct
5 Correct 34 ms 14704 KB Output is correct
6 Correct 27 ms 13368 KB Output is correct
7 Correct 28 ms 13628 KB Output is correct
8 Correct 33 ms 14084 KB Output is correct
9 Correct 31 ms 14252 KB Output is correct
10 Correct 27 ms 13924 KB Output is correct
11 Correct 28 ms 13948 KB Output is correct
12 Correct 27 ms 13912 KB Output is correct
13 Correct 27 ms 13892 KB Output is correct
14 Correct 32 ms 14376 KB Output is correct
15 Correct 30 ms 14032 KB Output is correct
16 Correct 23 ms 11856 KB Output is correct
17 Correct 24 ms 11748 KB Output is correct
18 Correct 27 ms 11612 KB Output is correct
19 Correct 24 ms 11708 KB Output is correct
20 Correct 37 ms 12632 KB Output is correct
21 Correct 26 ms 12220 KB Output is correct
22 Correct 30 ms 14208 KB Output is correct
23 Correct 24 ms 11964 KB Output is correct
24 Correct 25 ms 11948 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1056 KB Output is correct
2 Correct 1 ms 796 KB Output is correct
3 Correct 2 ms 1048 KB Output is correct
4 Correct 2 ms 1056 KB Output is correct
5 Correct 2 ms 1040 KB Output is correct
6 Correct 2 ms 1048 KB Output is correct
7 Correct 2 ms 1048 KB Output is correct
8 Correct 1 ms 1056 KB Output is correct
9 Correct 2 ms 1040 KB Output is correct
10 Correct 2 ms 1048 KB Output is correct
11 Correct 1 ms 1056 KB Output is correct
12 Correct 2 ms 1056 KB Output is correct
13 Correct 2 ms 1048 KB Output is correct
14 Correct 0 ms 1048 KB Output is correct
15 Correct 2 ms 1296 KB Output is correct
16 Correct 1 ms 1056 KB Output is correct
17 Correct 2 ms 1056 KB Output is correct
18 Correct 1 ms 1040 KB Output is correct
19 Correct 2 ms 1048 KB Output is correct
20 Correct 2 ms 1356 KB Output is correct
21 Correct 1 ms 1040 KB Output is correct
22 Correct 2 ms 1048 KB Output is correct
23 Correct 2 ms 1052 KB Output is correct
24 Correct 2 ms 1056 KB Output is correct
25 Correct 2 ms 1056 KB Output is correct
26 Correct 2 ms 1056 KB Output is correct
27 Correct 2 ms 1056 KB Output is correct
28 Correct 2 ms 1060 KB Output is correct

Subtask #6
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 11676 KB Output is correct
2 Correct 33 ms 12124 KB Output is correct
3 Correct 0 ms 788 KB Output is correct
4 Correct 20 ms 11548 KB Output is correct
5 Correct 31 ms 12756 KB Output is correct
6 Correct 36 ms 12600 KB Output is correct
7 Correct 26 ms 11632 KB Output is correct
8 Correct 28 ms 11812 KB Output is correct
9 Correct 32 ms 12648 KB Output is correct
10 Correct 31 ms 12680 KB Output is correct
11 Correct 30 ms 12636 KB Output is correct
12 Correct 31 ms 13056 KB Output is correct
13 Correct 30 ms 12616 KB Output is correct
14 Correct 30 ms 12676 KB Output is correct
15 Correct 30 ms 12664 KB Output is correct
16 Correct 30 ms 12840 KB Output is correct
17 Correct 31 ms 12412 KB Output is correct
18 Incorrect 28 ms 12412 KB Wrong Answer [6]
19 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 11604 KB Output is correct
2 Correct 27 ms 12124 KB Output is correct
3 Correct 0 ms 784 KB Output is correct
4 Correct 20 ms 11748 KB Output is correct
5 Correct 33 ms 12600 KB Output is correct
6 Incorrect 28 ms 12672 KB Wrong Answer [6]
7 Halted 0 ms 0 KB -