제출 #896191

#제출 시각아이디문제언어결과실행 시간메모리
896191jay_jayjayBitaro’s Party (JOI18_bitaro)C++14
14 / 100
2045 ms26980 KiB
// {{{1 extern "C" int __lsan_is_turned_off() { return 1; } #include <bits/stdc++.h> using namespace std; #define ll long long #define inf 0x3f3f3f3f #define infl 0x3f3f3f3f3f3f3f3fll #include <assert.h> #ifdef DEBUG #define dprintf(args...) fprintf(stderr,args) #endif #ifndef DEBUG #define dprintf(args...) 69 #endif #define all(x) (x).begin(), (x).end() #pragma GCC optimize("Ofast,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #define ll long long #include <stdio.h> #include <stdlib.h> // china io template #define BUFSZ (1<<22) char ibuf[BUFSZ],obuf[BUFSZ]; char* ip=ibuf+BUFSZ, * op=obuf; #define gc() (ip<ibuf+BUFSZ?*ip++:(fread(ip=ibuf,1,BUFSZ,stdin),*ip++)) ll read() { char c; int sgn=0; while((c=gc())<'0')sgn|=c=='-'; ll x=-(c-'0'); while((c=gc())>' ')x=x*10-(c-'0'); return sgn?x:-x; } char* read_str(char* x) { // note no null termination; returns past-end pointer char c; while((c=gc())<=' '); *x++=c; while((c=gc())>' ')*x++=c; return x; } void write_(ll x) { if(x<-9) write_(x/10); *op++=-(x%10)+'0'; } void write(ll x) { if(x<0) return *op++='-',write_(x); write_(-x); } void write_str(char* x) { while((*op++=*x++)); op--; } void flush() { fwrite(obuf,1,op-obuf,stdout), op=obuf; } #ifdef CHINAIO_TEST int main() { ll x=read();write(x); *op++='\n'; flush(); char buf[20]; char* e=read_str(buf); *e++=0; write_str(buf); *op++='\n'; flush(); } #endif // 1}}} struct { operator ll() { return read(); } } in; #define N 200000 vector<int> adj[N]; vector<array<int,2>> best[N]; int vis[N], bes[N]; #define B 300 #define B 3 int main() { int n=in,m=in,qq=in; while(m--) { int u=in,v=in;u--;v--; adj[v].push_back(u); } //for(int i=n-1;~i;i--) { for(int i=0;i<n;i++){ vector<int> pros; for(auto x:adj[i]) { for(auto [j,d]:best[x]) { if(vis[j]==i) bes[j]=max(bes[j],d+1); else bes[j]=d+1,vis[j]=i,pros.push_back(j); } } pros.push_back(i); bes[i]=0; //sort(all(pros),[&](int a, int b) { return bes[a]>bes[b]; }); int m=min((int)pros.size(),B); nth_element(pros.begin(),pros.begin()+m,pros.end(),[&](int a, int b) { return bes[a]>bes[b]; }); pros.resize(m); best[i].resize(m); for(int j=0;j<m;j++) { best[i][j] = {pros[j],bes[pros[j]]}; //printf("%d:\t%d, %d\n",i,pros[j],bes[pros[j]]); } //printf("\n"); } while(qq--) { int v=in,num=in;v--; //printf("\nquery v=%d num=%d\n",v,num); vector<int> ex(num);for(auto&x:ex)x=in,x--; sort(all(ex)); #define exl(i) ({auto it=lower_bound(all(ex),i); it!=ex.end()&&*it==i;}) if(num >= B) { // 用暴力 vector<int> bes(n,-1); for(int i=0;i<n;i++) { if(!exl(i)) bes[i]=0; for(auto x:adj[i]) if(bes[x]!=-1) bes[i] = max(bes[i],bes[x]+1); } printf("%d\n",bes[v]); } else { int bes=-1; for(auto [i, d] : best[v]) { if(!exl(i)) bes = max(d,bes); //printf("%d, %d (excluded:%d)\n",i,d,exl(i)); } printf("%d\n",bes); } } }

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

bitaro.cpp:88: warning: "B" redefined
   88 | #define B 3
      | 
bitaro.cpp:87: note: this is the location of the previous definition
   87 | #define B 300
      | 
bitaro.cpp: In function 'int main()':
bitaro.cpp:103:34: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  103 |                         for(auto [j,d]:best[x]) {
      |                                  ^
bitaro.cpp:140:34: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  140 |                         for(auto [i, d] : best[v]) {
      |                                  ^
bitaro.cpp: In function 'long long int read()':
bitaro.cpp:28:41: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 | #define gc() (ip<ibuf+BUFSZ?*ip++:(fread(ip=ibuf,1,BUFSZ,stdin),*ip++))
      |                                    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:33:18: note: in expansion of macro 'gc'
   33 |         while((c=gc())<'0')sgn|=c=='-';
      |                  ^~
bitaro.cpp:28:41: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 | #define gc() (ip<ibuf+BUFSZ?*ip++:(fread(ip=ibuf,1,BUFSZ,stdin),*ip++))
      |                                    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:35:18: note: in expansion of macro 'gc'
   35 |         while((c=gc())>' ')x=x*10-(c-'0');
      |                  ^~
bitaro.cpp: In function 'char* read_str(char*)':
bitaro.cpp:28:41: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 | #define gc() (ip<ibuf+BUFSZ?*ip++:(fread(ip=ibuf,1,BUFSZ,stdin),*ip++))
      |                                    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:40:18: note: in expansion of macro 'gc'
   40 |         while((c=gc())<=' ');
      |                  ^~
bitaro.cpp:28:41: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 | #define gc() (ip<ibuf+BUFSZ?*ip++:(fread(ip=ibuf,1,BUFSZ,stdin),*ip++))
      |                                    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:42:18: note: in expansion of macro 'gc'
   42 |         while((c=gc())>' ')*x++=c;
      |                  ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...