Submission #1082488

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082488		nikd	The Ties That Guide Us (CEOI23_incursion)	C++17	100 / 100	281 ms	14748 KiB

incursion

#include "incursion.h"
#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> adj1;
vector<int> siz;
vector<int> marked;
int n;

void calcsiz(int v, int e){
  siz[v]=1;
  for(int u: adj1[v]){
    if(u==e) continue;
    calcsiz(u, v);
    siz[v]+=siz[u];
  }
  return;
}

void dfsmark(int v, int e){
  int f1, f2;
  f1 = f2 = -1;
  for(int u: adj1[v]){
    if(u==e) continue;
    if(f1!=-1) f2 = u;
    else f1 = u;
    dfsmark(u, v);
  }
  int var = n- (f1!=-1 ? siz[f1] : 0) - (f2!=-1 ? siz[f2] : 0)-1;
  if(f1!=-1 && siz[f1]>=var){
    marked[v]=0;
  }
  if(f2!=-1 && siz[f2]>=var){
    marked[v]=0;
  }
  return;
}



vector<int> mark(vector<pair<int, int>> F, int safe) {
    n = F.size()+1;
    safe--;
    adj1.resize(n);
    /*for(int i = 0; i<n-1; i++){
      if(F[i].first == 0 || F[i].second == 0) while(1);
    }*/
    for(int i = 0; i<n-1; i++){
      adj1[F[i].first-1].push_back(F[i].second-1);
      adj1[F[i].second-1].push_back(F[i].first-1);
    }
    
    siz.resize(n);
    calcsiz(safe, safe);
    marked.resize(n, 1);
    marked[safe]=0;
    for(int u: adj1[safe]){
      dfsmark(u, safe);
    }
    return marked;
}

vector<vector<pair<int, int>>> adj2;
vector<int> vis;



void calcsiz2(int v, int e){
  siz[v]=1;
  for(auto eg: adj2[v]){
    int u = eg.first;
    if(u==e) continue;
    calcsiz2(u, v);
    siz[v]+=siz[u];
  }
  return;
}

void calcsiz3(int v, int e){
  int var = 0;
  for(auto& eg: adj2[v]){
    int u = eg.first;
    if(u==e){
      continue;
    }
    calcsiz3(u, v);
    eg.second = siz[u];
    var += siz[u];
  }
  for(auto& eg: adj2[v]){
    int u = eg.first;
    if(u==e){
      eg.second = n-var-1;
    }
  }
  return;
}

int real_pos;

int visit2(int v){
  if(vis[v]==-1){
    real_pos = v;
    return vis[v] = visit(v+1);
  }
  return vis[v];
}

void locate(vector<pair<int, int>> F, int curr, int t) {
  n = F.size()+1;
  adj2.resize(n);
  vis.resize(n, -1);
  for(int i = 0; i<n-1; i++){
    adj2[F[i].first-1].push_back({F[i].second-1, -1});
    adj2[F[i].second-1].push_back({F[i].first-1, -1});
  }
  curr--;
  siz.resize(n);
  calcsiz2(curr, curr); //segfaulta
  calcsiz3(curr, curr);
  int v = curr;
  real_pos = v;
  vis[curr]=t;
  while(1){
    sort(adj2[v].begin(), adj2[v].end(), [](auto a, auto b){
      return a.second > b.second;
    });
    if(t){
      v = adj2[v][0].first;
      t = visit2(v);
    }
    else{
      if(adj2[v].size()<2) return;
      if(adj2[v][0].second==adj2[v][1].second){
        t = visit2(adj2[v][0].first);
        if(t==1){
          t = visit2(v);
          if(real_pos!=v){
            visit(v+1);
            real_pos = v;
          }

          if(adj2[v].size()<2) return;
          t = visit2(adj2[v][1].first);
          if(t==1){
            t = visit2(v);
            if(real_pos!=v){
              visit(v+1);
              real_pos = v;
            } 
            if(adj2[v].size()<3) return;
            t = visit2(adj2[v][2].first);
            if(t==1){
              visit2(v);
              if(real_pos!=v){
                visit(v+1);
                real_pos = v;
              } 
              return;
            }
            else v = adj2[v][2].first;
          }
          else v = adj2[v][1].first;
        }
        else v = adj2[v][0].first;
      }

      else{
      t = visit2(adj2[v][1].first);
      if(t==1){
        t = visit2(v);
        if(real_pos!=v){
          visit(v+1);
          real_pos = v;
        }
        if(adj2[v].size()<3) return;
        t = visit2(adj2[v][2].first);
        if(t==1){
          visit2(v); 
          if(real_pos!=v){
            visit(v+1);
            real_pos = v;
          }
          return;
        }
        else v = adj2[v][2].first;
      }
      else v = adj2[v][1].first;
      }
    }
    

  }
} 

Compilation message (stderr)

interface.cpp: In function 'int main()':
interface.cpp:44:55: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   44 |     if(fread(T.data(), sizeof(int), 2 * N - 2, stdin) != 2 * N - 2) exit(0);
      |        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
interface.cpp:50:33: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   50 |         int l = (numbers.size() == N ? N : 0);
      |                  ~~~~~~~~~~~~~~~^~~~

• Subtask 0: 0 / 0
• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40