Submission #896192

#	Time	Username	Problem	Language	Result	Execution time	Memory
896192		jay_jayjay	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1012 ms	260652 KiB

bitaro

// {{{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);
                }
        }
}

Compilation message (stderr)

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;
      |                  ^~

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 86 / 86