Submission #1081404

#	Time	Username	Problem	Language	Result	Execution time	Memory
1081404		veehj	The Ties That Guide Us (CEOI23_incursion)	C++17	9 / 100	287 ms	7564 KiB

incursion

#include "incursion.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define F first
#define S second
#define pb push_back
#define sz(a) (int)a.size()
#define all(x) (x).begin(), (x).end()

vector<int> mark(vector<pair<int, int>> f, int safe) {
  vector<vector<int>> adj(f.size()+1, vector<int>(0));
  vector<int> ans(f.size()+1, -1);
  for(auto& u : f){
      u.F--; u.S--;
      adj[u.F].pb(u.S);
      adj[u.S].pb(u.F);
  }
  ans.assign(f.size()+1, -1);
  safe--;
  priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
  q.push({0, safe});
  ans[safe]=0;
  while(!q.empty()){
    int nw=q.top().S;
    if(ans[nw]<q.top().F){
      q.pop();
      continue;
    }
    q.pop();
    for(auto& u : adj[nw]){
      if(ans[u]==-1 || ans[u]>ans[nw]+1){
        ans[u]=ans[nw]+1;
        q.push({ans[u], u});
      }
    }
  }
  for(auto& u : ans) u%=3;
  ans[safe]=3;
  return ans;
}

void locate(vector<pair<int, int>> f, int curr, int t) {
  map<int, int> mp={{0, 2}, {1, 0}, {2, 1}};
  vector<vector<int>> adj(f.size()+1, vector<int>(0));
  vector<bool> vist(f.size()+1, 0);
  for(auto& u : f){
      u.F--; u.S--;
      adj[u.F].pb(u.S);
      adj[u.S].pb(u.F);
  }
  curr--;
  int lst=curr, lstdeg=t;
  for(auto& u : adj[curr]){
    if(vist[u]) continue;
    lst=curr;
    lstdeg=t;
    t=visit(u+1);
    curr=u;
    break;
  }
  while(t!=3){
    vist[curr]=1;
    if(t!=mp[lstdeg]){
      for(auto& u : adj[curr]){
        vist[u]=1;
      }
      t=visit(lst+1);
      curr=lst;
    }
    for(auto& u : adj[curr]){
      if(vist[u]) continue;
      lst=curr;
      lstdeg=t;
      t=visit(u+1);
      curr=u;
      break;
    }
  }
  return;
}

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: 9 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40