oj.uz

Submission #1040726

# Submission time Handle Problem Language Result Execution time Memory
1040726 2024-08-01T08:45:30 Z 비요뜨(#11041) The Ties That Guide Us (CEOI23_incursion) C++17
0 / 100
 136 ms 14416 KB 
#include <vector>
#include "incursion.h"
#include <bits/stdc++.h>
using namespace std;

int p[45001];
int vis[45001];
vector<int> adj[45001];
int sz[45001];

void dfs(int v,int pr) {
    p[v]=pr;
    sz[v]=1;
    for(int i=0;i<adj[v].size();i++) {
        int nt=adj[v][i];
        if (nt!=pr) {
            dfs(nt,v);
            sz[v]+=sz[nt];
        }
    }
}

std::vector<int> mark(std::vector<std::pair<int, int>> F, int safe) {
  int n=F.size()+1;
  int r;
  for(int i=0;i<F.size();i++) {
      adj[F[i].first].push_back(F[i].second);
      adj[F[i].second].push_back(F[i].first);
  }
  for(int i=1;i<=n;i++) {
      if (adj[i].size()==2) {
          r=i;
      }
  }
  dfs(r,-1);
  vector<int> v(n);
  for(int i=0;i<n;i++) {
      v[i]=1;
  }
  int now=safe;
  v[safe-1]=0;
  int pr=-1;
  while (now!=r) {
      pr=now;
      now=p[now];
      int ot;
      for(int i=0;i<adj[now].size();i++) {
          if (adj[now][i]!=p[now]&&adj[now][i]!=pr) {
              ot=pr;
              break;
          }
      }
      if (sz[ot]>sz[pr]) {
          v[now-1]=1;
      }
      else {
          v[now-1]=0;
      }
  }
  if (safe==r) {
      v[safe-1]=1;
  }
  return v;
}

void locate(std::vector<std::pair<int, int>> F, int curr, int t) {
    int n=F.size()+1;
    int fc=0;
    int r;
    for(int i=1;i<=n;i++) {
        adj[i].clear();
        sz[i]=0;
    }
  for(int i=0;i<F.size();i++) {
      adj[F[i].first].push_back(F[i].second);
      adj[F[i].second].push_back(F[i].first);
  }
  for(int i=1;i<=n;i++) {
      if (adj[i].size()==2) {
          r=i;
      }
  }
  dfs(r,-1);
  int now=curr;
  int val=t;
  memset(vis,0,sizeof(vis));
  while (1) {
      vis[now]++;
      bool flag=false;
      if (now==r&&val==1) {
          flag=true;
      }
      //printf("%d %d\n",now,val);
      if (val==1) {
          //printf(".\n");
          val=visit(p[now]);
          now=p[now];
          continue;
      }
      int nxt=-1;
      int ot=-1;
      for(int i=0;i<adj[now].size();i++) {
          int nt=adj[now][i];
          if (nt!=p[now]&&vis[nt]<2) {
              if (nxt==-1) {
                  nxt=nt;
              }
              else {
                  ot=nt;
              }
          }
      }
      if (nxt==-1) {
          return;
      }
      //printf(".%d %d\n",nxt,ot);
      if (flag) {
          if (ot==-1||sz[nxt]<sz[ot]) {
              val=visit(nxt);
              now=nxt;
          }
          else {
              val=visit(ot);
              now=ot;
          }
          continue;
      }
      if (ot==-1||sz[nxt]>sz[ot]) {
          val=visit(nxt);
          now=nxt;
      }
      else {
          val=visit(ot);
          now=ot;
      }
  }
  return;
}

Compilation message

incursion.cpp: In function 'void dfs(int, int)':
incursion.cpp:14:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |     for(int i=0;i<adj[v].size();i++) {
      |                 ~^~~~~~~~~~~~~~
incursion.cpp: In function 'std::vector<int> mark(std::vector<std::pair<int, int> >, int)':
incursion.cpp:26:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |   for(int i=0;i<F.size();i++) {
      |               ~^~~~~~~~~
incursion.cpp:47:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |       for(int i=0;i<adj[now].size();i++) {
      |                   ~^~~~~~~~~~~~~~~~
incursion.cpp: In function 'void locate(std::vector<std::pair<int, int> >, int, int)':
incursion.cpp:74:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |   for(int i=0;i<F.size();i++) {
      |               ~^~~~~~~~~
incursion.cpp:102:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |       for(int i=0;i<adj[now].size();i++) {
      |                   ~^~~~~~~~~~~~~~~~
incursion.cpp:68:9: warning: unused variable 'fc' [-Wunused-variable]
   68 |     int fc=0;
      |         ^~
incursion.cpp: In function 'std::vector<int> mark(std::vector<std::pair<int, int> >, int)':
incursion.cpp:35:6: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
   35 |   dfs(r,-1);
      |   ~~~^~~~~~
incursion.cpp:53:16: warning: 'ot' may be used uninitialized in this function [-Wmaybe-uninitialized]
   53 |       if (sz[ot]>sz[pr]) {
      |           ~~~~~^
incursion.cpp: In function 'void locate(std::vector<std::pair<int, int> >, int, int)':
incursion.cpp:83:6: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
   83 |   dfs(r,-1);
      |   ~~~^~~~~~
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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3076 KB Correct

Subtask #1
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 35 ms 14416 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 8188 KB Correct
2 Correct 63 ms 8336 KB Correct
3 Correct 69 ms 8076 KB Correct
4 Correct 66 ms 11408 KB Correct
5 Correct 108 ms 11736 KB Correct
6 Correct 136 ms 11680 KB Correct
7 Correct 61 ms 7860 KB Correct
8 Correct 57 ms 8008 KB Correct
9 Correct 63 ms 7848 KB Correct
10 Incorrect 67 ms 7812 KB Not correct
11 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3076 KB Correct
2 Runtime error 35 ms 14416 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -