제출 #285091

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

이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.

bitaro

using namespace std; const int THRESH = 160; vector<int> ord; vector<int> g[100005]; vector<int> rg[100005]; bool found[100005]; void dfs(int u){ if(found[u]) return; found[u] = true; for(int v : g[u]){ dfs(v); } ord.push_back(u); } vector<pair<int,int> > dp[100005]; // | dp[i] | <= THRESH. bool __used[100005]; vector<pair<int,int> > newVec; void __append(pair<int,int> x){ if(newVec.empty() || !__used[x.second]){ newVec.push_back(x); __used[x.second] = true; } } void merge(vector<pair<int,int> >& dest, vector<pair<int,int> > src){ for(auto& v : src) v.first++; int ptr1 = 0; int ptr2 = 0; while(ptr1 < dest.size() && ptr2 < src.size() && newVec.size() < THRESH){ if(dest[ptr1] > src[ptr2]){ __append(dest[ptr1]); ptr1++; }else{ __append(src[ptr2]); ptr2++; } } while(newVec.size() < THRESH && ptr1 < dest.size()){ __append(dest[ptr1]); ptr1++; } while(newVec.size() < THRESH && ptr2 < src.size()){ __append(src[ptr2]); ptr2++; } for(auto u : newVec) __used[u.second] = false; swap(dest, newVec); newVec.clear(); } bool isBusy[100005]; int subdp[100005]; int recalculateAnswer(int t){ for(int u : ord){ subdp[u] = isBusy[u] ? -10000000 : 0; for(int v : rg[u]){ subdp[u] = max(subdp[u], subdp[v]+1); } } return subdp[t] < 0 ? -1 : subdp[t]; } int main(){ int n, m, q; scanf("%d%d%d",&n,&m,&q); for(int i = 0; i < m; i++){ int s,e; scanf("%d%d",&s,&e); g[s].push_back(e); rg[e].push_back(s); } for(int i = 1; i <= n; i++) dfs(i); reverse(ord.begin(), ord.end()); for(int u : ord){ for(int v : rg[u]){ merge(dp[u], dp[v]); } merge(dp[u], {make_pair(-1, u)}); /* printf("DBG [%d]\n", u); for(auto v : dp[u]){ printf("%d %d\n", v.first, v.second); } */ } int t, y; for(int qq = 0; qq < q; qq++){ scanf("%d%d",&t,&y); vector<int> busy; busy.reserve(y); for(int i = 0; i < y; i++){ int c; scanf("%d",&c); busy.push_back(c); isBusy[c] = true; } int ans = -1; if(y < THRESH-1){ for(auto p : dp[t]){ if(isBusy[p.second]) continue; ans = p.first; break; } }else{ ans = recalculateAnswer(t); } for(int c : busy) isBusy[c] = false; printf("%d\n",ans); } return 0; }

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

bitaro.cpp:3:1: error: 'vector' does not name a type
    3 | vector<int> ord;
      | ^~~~~~
bitaro.cpp:4:1: error: 'vector' does not name a type
    4 | vector<int> g[100005];
      | ^~~~~~
bitaro.cpp:5:1: error: 'vector' does not name a type
    5 | vector<int> rg[100005];
      | ^~~~~~
bitaro.cpp: In function 'void dfs(int)':
bitaro.cpp:10:14: error: 'g' was not declared in this scope
   10 |  for(int v : g[u]){
      |              ^
bitaro.cpp:13:2: error: 'ord' was not declared in this scope
   13 |  ord.push_back(u);
      |  ^~~
bitaro.cpp: At global scope:
bitaro.cpp:15:1: error: 'vector' does not name a type
   15 | vector<pair<int,int> > dp[100005]; // | dp[i] | <= THRESH.
      | ^~~~~~
bitaro.cpp:17:1: error: 'vector' does not name a type
   17 | vector<pair<int,int> > newVec;
      | ^~~~~~
bitaro.cpp:18:15: error: variable or field '__append' declared void
   18 | void __append(pair<int,int> x){
      |               ^~~~
bitaro.cpp:18:15: error: 'pair' was not declared in this scope
bitaro.cpp:1:1: note: 'std::pair' is defined in header '<utility>'; did you forget to '#include <utility>'?
  +++ |+#include <utility>
    1 | using namespace std;
bitaro.cpp:18:20: error: expected primary-expression before 'int'
   18 | void __append(pair<int,int> x){
      |                    ^~~
bitaro.cpp:18:24: error: expected primary-expression before 'int'
   18 | void __append(pair<int,int> x){
      |                        ^~~
bitaro.cpp:24:12: error: variable or field 'merge' declared void
   24 | void merge(vector<pair<int,int> >& dest, vector<pair<int,int> > src){
      |            ^~~~~~
bitaro.cpp:24:12: error: 'vector' was not declared in this scope
bitaro.cpp:1:1: note: 'std::vector' is defined in header '<vector>'; did you forget to '#include <vector>'?
  +++ |+#include <vector>
    1 | using namespace std;
bitaro.cpp:24:19: error: 'pair' was not declared in this scope
   24 | void merge(vector<pair<int,int> >& dest, vector<pair<int,int> > src){
      |                   ^~~~
bitaro.cpp:24:19: note: 'std::pair' is defined in header '<utility>'; did you forget to '#include <utility>'?
bitaro.cpp:24:24: error: expected primary-expression before 'int'
   24 | void merge(vector<pair<int,int> >& dest, vector<pair<int,int> > src){
      |                        ^~~
bitaro.cpp:24:28: error: expected primary-expression before 'int'
   24 | void merge(vector<pair<int,int> >& dest, vector<pair<int,int> > src){
      |                            ^~~
bitaro.cpp:24:42: error: 'vector' was not declared in this scope
   24 | void merge(vector<pair<int,int> >& dest, vector<pair<int,int> > src){
      |                                          ^~~~~~
bitaro.cpp:24:42: note: 'std::vector' is defined in header '<vector>'; did you forget to '#include <vector>'?
bitaro.cpp:24:49: error: 'pair' was not declared in this scope
   24 | void merge(vector<pair<int,int> >& dest, vector<pair<int,int> > src){
      |                                                 ^~~~
bitaro.cpp:24:49: note: 'std::pair' is defined in header '<utility>'; did you forget to '#include <utility>'?
bitaro.cpp:24:54: error: expected primary-expression before 'int'
   24 | void merge(vector<pair<int,int> >& dest, vector<pair<int,int> > src){
      |                                                      ^~~
bitaro.cpp:24:58: error: expected primary-expression before 'int'
   24 | void merge(vector<pair<int,int> >& dest, vector<pair<int,int> > src){
      |                                                          ^~~
bitaro.cpp: In function 'int recalculateAnswer(int)':
bitaro.cpp:52:14: error: 'ord' was not declared in this scope
   52 |  for(int u : ord){
      |              ^~~
bitaro.cpp:54:15: error: 'rg' was not declared in this scope
   54 |   for(int v : rg[u]){
      |               ^~
bitaro.cpp:55:15: error: 'max' was not declared in this scope
   55 |    subdp[u] = max(subdp[u], subdp[v]+1);
      |               ^~~
bitaro.cpp: In function 'int main()':
bitaro.cpp:62:2: error: 'scanf' was not declared in this scope
   62 |  scanf("%d%d%d",&n,&m,&q);
      |  ^~~~~
bitaro.cpp:66:3: error: 'g' was not declared in this scope
   66 |   g[s].push_back(e);
      |   ^
bitaro.cpp:67:3: error: 'rg' was not declared in this scope
   67 |   rg[e].push_back(s);
      |   ^~
bitaro.cpp:70:10: error: 'ord' was not declared in this scope
   70 |  reverse(ord.begin(), ord.end());
      |          ^~~
bitaro.cpp:70:2: error: 'reverse' was not declared in this scope
   70 |  reverse(ord.begin(), ord.end());
      |  ^~~~~~~
bitaro.cpp:72:15: error: 'rg' was not declared in this scope
   72 |   for(int v : rg[u]){
      |               ^~
bitaro.cpp:73:10: error: 'dp' was not declared in this scope
   73 |    merge(dp[u], dp[v]);
      |          ^~
bitaro.cpp:73:4: error: 'merge' was not declared in this scope
   73 |    merge(dp[u], dp[v]);
      |    ^~~~~
bitaro.cpp:75:9: error: 'dp' was not declared in this scope
   75 |   merge(dp[u], {make_pair(-1, u)});
      |         ^~
bitaro.cpp:75:17: error: 'make_pair' was not declared in this scope
   75 |   merge(dp[u], {make_pair(-1, u)});
      |                 ^~~~~~~~~
bitaro.cpp:75:17: note: 'std::make_pair' is defined in header '<utility>'; did you forget to '#include <utility>'?
bitaro.cpp:75:3: error: 'merge' was not declared in this scope
   75 |   merge(dp[u], {make_pair(-1, u)});
      |   ^~~~~
bitaro.cpp:86:3: error: 'vector' was not declared in this scope
   86 |   vector<int> busy;
      |   ^~~~~~
bitaro.cpp:86:3: note: 'std::vector' is defined in header '<vector>'; did you forget to '#include <vector>'?
bitaro.cpp:86:10: error: expected primary-expression before 'int'
   86 |   vector<int> busy;
      |          ^~~
bitaro.cpp:87:3: error: 'busy' was not declared in this scope
   87 |   busy.reserve(y);
      |   ^~~~
bitaro.cpp:96:17: error: 'dp' was not declared in this scope; did you mean 'p'?
   96 |    for(auto p : dp[t]){
      |                 ^~
      |                 p
bitaro.cpp:105:3: error: 'printf' was not declared in this scope
  105 |   printf("%d\n",ans);
      |   ^~~~~~
bitaro.cpp:1:1: note: 'printf' is defined in header '<cstdio>'; did you forget to '#include <cstdio>'?
  +++ |+#include <cstdio>
    1 | using namespace std;