제출 #1332354

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1332354		julia_08	Bitaro’s Party (JOI18_bitaro)	C++20	컴파일 에러	0 ms	0 KiB

bitaro

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

const int MAXN = 1e5 + 10;
const int SQ = 1e5 + 10;

int dist[MAXN], marc[MAXN];

int vis[MAXN], in[MAXN];

vector<int> adj[MAXN];

pair<int, int> dp[MAXN][SQ];

int n, m, q;

void bfs(int s){

  queue<int> q;

  for(int i=1; i<=n; i++) marc[i] = 0;

  q.push(s);
  dist[s] = 0; marc[s] = 1;

  while(!q.empty()){

    int v = q.front();
    q.pop();

    for(auto u : adj[v]){
      if(!marc[u]){
        marc[u] = 1;
        dist[u] = dist[v] + 1;
        q.push(u);
      }
    }

  }

}

void merge(int u, int v){

  int l = 0, r = 0;

  vector<pair<int, int>> cur;

  for(int i=0; i<SQ; i++) vis[dp[u][i].first] = vis[dp[v][i].first] = 0;

  while((int) cur.size() < SQ){

    while(l < SQ && vis[dp[v][r].first]) r++;
    while(r < SQ && vis[dp[u][l].first]) l++;

    if(r < SQ && dp[v][r].second + 1 > dp[u][l].second){

      cur.push_back({dp[v][r].first, dp[v][r].second + 1});
      r++;
    
    } else cur.push_back(dp[u][l++]);

    if(cur.back().first > 0) vis[cur.back().first] = 1;

  }

  for(int i=0; i<SQ; i++) dp[u][i] = cur[i];

}

void pre_bfs(){

  queue<int> q;

  for(int i=1; i<=n; i++){

    dp[i][0] = {i, 0};

    for(int j=1; j<SQ; j++) dp[i][j] = {0, -1e9};

    if(in[i] == 0) q.push(i);

  }

  while(!q.empty()){

    int v = q.front();
    q.pop();

    for(auto u : adj[v]){

      in[u] --;

      merge(u, v);
      if(in[u] == 0) q.push(u);

    }

  }

}

int main(){
  cin.tie(0)->sync_with_stdio(0);

  cin >> n >> m >> q;

  while(m--){

    int a, b; cin >> a >> b;    
  
    adj[a].push_back(b);
    in[b] ++;

  }

  pre_bfs();

  vector<int> vis, to_skip(n + 1, 0);

  for(int i=0; i<q; i++){

    int t, y; cin >> t >> y;

    vis.resize(y);

    for(int j=0; j<y; j++){
      cin >> vis[j];
      to_skip[vis[j]] = 1;
    }

    if(y < SQ){

      int x = 0;

      while(to_skip[dp[t][x].first]) x++;

      cout << max(-1, dp[t][x].second) << "\n";

    } else{

      bfs(t);

      int ans = 0;

      for(int j=1; j<=n; j++) if(!to_skip[j]) ans = max(ans, dist[j]);

      cout << ans << "\n";

    }

    for(int j=0; j<y; j++) to_skip[vis[j]] = 0;

  }

  return 0;
}

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

/tmp/ccjJRfSL.o: in function `__tcf_0':
bitaro.cpp:(.text+0x9): relocation truncated to fit: R_X86_64_PC32 against symbol `adj' defined in .bss section in /tmp/ccjJRfSL.o
/tmp/ccjJRfSL.o: in function `merge(int, int)':
bitaro.cpp:(.text+0x93): relocation truncated to fit: R_X86_64_PC32 against symbol `vis' defined in .bss section in /tmp/ccjJRfSL.o
/tmp/ccjJRfSL.o: in function `bfs(int)':
bitaro.cpp:(.text+0x660): relocation truncated to fit: R_X86_64_PC32 against symbol `marc' defined in .bss section in /tmp/ccjJRfSL.o
bitaro.cpp:(.text+0x694): relocation truncated to fit: R_X86_64_PC32 against symbol `dist' defined in .bss section in /tmp/ccjJRfSL.o
bitaro.cpp:(.text+0x69b): relocation truncated to fit: R_X86_64_PC32 against symbol `marc' defined in .bss section in /tmp/ccjJRfSL.o
bitaro.cpp:(.text+0x6af): relocation truncated to fit: R_X86_64_PC32 against symbol `adj' defined in .bss section in /tmp/ccjJRfSL.o
/tmp/ccjJRfSL.o: in function `pre_bfs()':
bitaro.cpp:(.text+0x8d5): relocation truncated to fit: R_X86_64_PC32 against symbol `in' defined in .bss section in /tmp/ccjJRfSL.o
bitaro.cpp:(.text+0x942): relocation truncated to fit: R_X86_64_PC32 against symbol `in' defined in .bss section in /tmp/ccjJRfSL.o
bitaro.cpp:(.text+0x973): relocation truncated to fit: R_X86_64_PC32 against symbol `adj' defined in .bss section in /tmp/ccjJRfSL.o
/tmp/ccjJRfSL.o: in function `main':
bitaro.cpp:(.text.startup+0xf): relocation truncated to fit: R_X86_64_PC32 against symbol `std::cin' defined in .bss._ZSt3cin section in /usr/lib/gcc/x86_64-linux-gnu/13/libstdc++.a(globals_io.o)
bitaro.cpp:(.text.startup+0x19): additional relocation overflows omitted from the output
/usr/lib/gcc/x86_64-linux-gnu/13/libstdc++.a(ios_init.o): in function `std::ios_base::Init::Init()':
(.text._ZNSt8ios_base4InitC2Ev+0x1f): failed to convert GOTPCREL relocation against '_ZNSt8ios_base4Init11_S_refcountE'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x1ed): failed to convert GOTPCREL relocation against '_ZSt4cout'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x252): failed to convert GOTPCREL relocation against '_ZSt3cin'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x2bc): failed to convert GOTPCREL relocation against '_ZSt4cerr'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x316): failed to convert GOTPCREL relocation against '_ZSt4clog'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x50f): failed to convert GOTPCREL relocation against '_ZSt5wcout'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x57d): failed to convert GOTPCREL relocation against '_ZSt4wcin'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x5f0): failed to convert GOTPCREL relocation against '_ZSt5wcerr'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x654): failed to convert GOTPCREL relocation against '_ZSt5wclog'; relink with --no-relax
/usr/bin/ld: final link failed
collect2: error: ld returned 1 exit status