제출 #1072173

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1072173		edogawa_something	The Ties That Guide Us (CEOI23_incursion)	C++17	9 / 100	285 ms	41256 KiB

incursion

#include "incursion.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vii;
typedef pair<ll,ll> pii;
#define F first
#define S second
#define all(v) v.begin(),v.end()
#define pb push_back
const ll M=5e5+10;
const ll inf=2e18;
vii adj[M];
bool vis[M];
ll dis[M],pa[M],dep[M];
void mdfs(ll x,ll d=0) {
  if(vis[x])
    return;
  vis[x]=1;
  dis[x]=d;
  for(auto it:adj[x]) {
    if(it==pa[x])
      continue;
    pa[it]=x;
    mdfs(it,d+1);
    dep[x]=max(dep[x],dep[it]+1);
  }
}
std::vector<int> mark(std::vector<std::pair<int, int>> F, int safe) {
  for(int i=0;i<F.size();i++)
    adj[F[i].F].pb(F[i].S),adj[F[i].S].pb(F[i].F);
  mdfs(safe);
  vector<int>res;
  for(int i=1;i<=F.size()+1;i++)
    res.pb(dis[i]);
  return res;
}

void locate(std::vector<std::pair<int, int>> F, int curr, int t) {
  for(int i=1;i<F.size()+2;i++)
    adj[i].clear();
  for(int i=0;i<F.size();i++)
    adj[F[i].F].pb(F[i].S),adj[F[i].S].pb(F[i].F);
  ll n=F.size()+1;
  for(int i=0;i<n;i++)
    vis[i+1]=pa[i+1]=dis[i+1]=dep[i+1]=0;
  mdfs(curr);
  ll lt=t;
  for(int i=1;i<=n;i++)
    vis[i]=0;
  while(t!=0) {
    for(auto it:adj[curr]) {
      //cout<<curr<<' '<<it<<' '<<dep[it]<<' '<<t<<endl;
      if(it==pa[curr]||dep[it]<t-1)
        continue;
      ll tt=visit(int(it));
      if(tt>t)
        visit(curr);
      else {
        t=tt;
        curr=it;
        break;
      }
    }
  }
}
/*
10 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10


*/

컴파일 시 표준 에러 (stderr) 메시지

incursion.cpp: In function 'std::vector<int> mark(std::vector<std::pair<int, int> >, int)':
incursion.cpp:30: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]
   30 |   for(int i=0;i<F.size();i++)
      |               ~^~~~~~~~~
incursion.cpp:34: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]
   34 |   for(int i=1;i<=F.size()+1;i++)
      |               ~^~~~~~~~~~~~
incursion.cpp: In function 'void locate(std::vector<std::pair<int, int> >, int, int)':
incursion.cpp:40: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]
   40 |   for(int i=1;i<F.size()+2;i++)
      |               ~^~~~~~~~~~~
incursion.cpp:42: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]
   42 |   for(int i=0;i<F.size();i++)
      |               ~^~~~~~~~~
incursion.cpp:46:21: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   46 |     vis[i+1]=pa[i+1]=dis[i+1]=dep[i+1]=0;
      |              ~~~~~~~^~~~~~~~~~~~~~~~~~~~
incursion.cpp:48:6: warning: unused variable 'lt' [-Wunused-variable]
   48 |   ll lt=t;
      |      ^~
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