제출 #1194523

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1194523		zNatsumi	Checker (COCI19_checker)	C++20	35 / 110	204 ms	47076 KiB

checker

#include <bits/stdc++.h>

using namespace std;

using ii = pair<int, int>;
const int N = 2e5 + 5;

int n, st[N<<2], depth[N], rt[N], up[N][20], timer, in[N], out[N];
bool vst[N];
vector<int> ad[N];
vector<ii> edge[3];

void update(int x, int y, int tl, int tr, int i){
  if(tl == tr){
    st[i] = max(st[i], y);
    return;
  }
  int tm = tl + tr >> 1;
  if(x <= tm) update(x, y, tl, tm, i<<1);
  else update(x, y, tm + 1, tr, i<<1|1);
  st[i] = max(st[i<<1], st[i<<1|1]);
}

int get(int l, int r, int tl, int tr, int i){
  if(r < tl || tr < l || l > r) return 0;
  if(l <= tl && tr <= r) return st[i];
  int tm = tl + tr >> 1;
  return max(get(l, r, tl, tm, i<<1), get(l, r, tm + 1, tr, i<<1|1));
}

void dfs(int u, int p, int root){
  in[u] = ++timer;
  vst[u] = true;
  rt[u] = root;
  for(int i = 1; i <= 17; i++) up[u][i] = up[up[u][i - 1]][i - 1];

  for(auto v : ad[u])
    if(v != p){
      if(vst[v]){
        cout << "neispravno bojenje";
        exit(0);
      }else{
        depth[v] = depth[u] + 1;
        up[v][0] = u;
        dfs(v, u, root);
      }
    }
  out[u] = ++timer;
}

bool anc(int u, int v){
  return in[u] <= in[v] && out[v] <= out[u];
}

int lca(int u, int v){
  if(anc(u, v)) return u;
  if(anc(v, u)) return v;
  for(int i = 17; i >= 0; i--)
    if(up[u][i] && !anc(up[u][i], v)) u = up[u][i];
  return up[u][0];
}

int dist(int u, int v){
  if(rt[u] != rt[v]) return -1;
  return depth[u] + depth[v] - depth[lca(u, v)];
}

void solve(int x){
  timer = 0;
  for(int i = 1; i <= n; i++){
    ad[i].clear();
    vst[i] = depth[i] = rt[i] = in[i] = out[i] = 0;
    for(int j = 0; j <= 17; j++) up[i][j] = 0;
  }
  for(auto [u, v] : edge[x]){
    ad[u].push_back(v);
    ad[v].push_back(u);
  }
  for(int i = 1; i <= n; i++) if(!vst[i]) dfs(i, i, i);
  for(int i = 0; i <= 2; i++) if(i != x)
    for(auto [u, v] : edge[i]) if(dist(u, v) == 2){
      cout << "neispravno bojenje";
      exit(0);
    }
}

int32_t main(){
  cin.tie(0)->sync_with_stdio(0);
//  #define task "test"
//  if(fopen(task ".inp", "r")){
//    freopen(task ".inp", "r", stdin);
//    freopen(task ".out", "w", stdout);
//  }
  int _; cin >> _;
  cin >> n;
  for(int i = 1; i <= n; i++){
    int v = i + 1 > n ? 1 : i + 1;
    char w; cin >> w; w -= '1';
    ad[i].push_back(v);
    ad[v].push_back(i);
    edge[w].push_back({i, v});
  }
  for(int i = 1; i <= n - 3; i++){
    int u, v, c; cin >> u >> v >> c;
    ad[u].push_back(v);
    ad[v].push_back(u);
    edge[c - 1].push_back({u, v});
  }
  for(int i = 1; i <= n; i++){
    int x = 0;
    for(auto v : ad[i])
      if(v > i) x = max(x, v);
      else if(get(v + 1, i - 1, 1, n, 1) > i) return cout << "neispravna triangulacija", 0;
    update(i, x, 1, n, 1);
  }
  for(int i = 0; i <= 2; i++) solve(i);
  cout << "tocno";
}

• Subtask 1: 12 / 12
• Subtask 2: 0 / 17
• Subtask 3: 23 / 23
• Subtask 4: 0 / 23
• Subtask 5: 0 / 35