Skip to content

Instantly share code, notes, and snippets.

@SamZhangQingChuan

SamZhangQingChuan/A.cpp

Created December 10, 2018 05:56
Show Gist options
  • Save SamZhangQingChuan/b1c6f0baa45779379485c866c9e77744 to your computer and use it in GitHub Desktop.
Save SamZhangQingChuan/b1c6f0baa45779379485c866c9e77744 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
A.cpp
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC optimize(3)
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC target("sse3","sse2","sse")
#pragma GCC target("avx","sse4","sse4.1","sse4.2","ssse3")
#pragma GCC target("f16c")
#pragma GCC optimize("inline","fast-math","unroll-loops","no-stack-protector")
#pragma GCC diagnostic error "-fwhole-program"
#pragma GCC diagnostic error "-fcse-skip-blocks"
#pragma GCC diagnostic error "-funsafe-loop-optimizations"
#pragma GCC diagnostic error "-std=c++14"
#include "bits/stdc++.h"
//#include "ext/pb_ds/tree_policy.hpp"
//#include "ext/pb_ds/assoc_container.hpp"
#define PB push_back
#define PF push_front
#define LB lower_bound
#define UB upper_bound
#define fr(x) freopen(x,"r",stdin)
#define fw(x) freopen(x,"w",stdout)
#define iout(x) printf("%d\n",x)
#define lout(x) printf("%lld\n",x)
#define REP(x,l,u) for(ll x = l;x<u;x++)
#define RREP(x,l,u) for(ll x = l;x>=u;x--)
#define complete_unique(a) a.erase(unique(a.begin(),a.end()),a.end())
#define mst(x,a) memset(x,a,sizeof(x))
#define all(a) a.begin(),a.end()
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define MP make_pair
#define sqr(x) ((x)*(x))
#define lowbit(x) ((x)&(-(x)))
#define lson (ind<<1)
#define rson (ind<<1|1)
#define se second
#define fi first
#define dbg(x) cerr<<#x<<" = "<<(x)<<endl;
#define sz(x) ((int)x.size())
#define EX0 exit(0);
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ld;
using namespace std;
typedef vector<ll> VLL;
typedef vector<int> VI;
const int block_size = 320;
typedef complex<ll> point;
const ll mod = 1e9+7;
const ll inf = 1e9+7;
const ld eps = 1e-9;
const db PI = atan(1)*4;
template<typename T>
inline int sign(const T&a) {
if(a<0)return -1;
if(a>0)return 1;
return 0;
}
template<typename T,typename S>inline bool upmin(T&a,const S&b){return a>b?a=b,1:0;}
template<typename T,typename S>inline bool upmax(T&a,const S&b){return a<b?a=b,1:0;}
template<typename T> inline void in(T &x) {
x = 0;
T f = 1;
char ch = getchar();
while (!isdigit(ch)) {
if (ch == '-') f = -1;
ch = getchar();
}
while (isdigit(ch)) {
x = x * 10 + ch - '0';
ch = getchar();
}
x *= f;
}
ll twop(int x) {
return 1LL<<x;
}
template<typename A,typename B > inline void in(A&x,B&y) {
in(x);
in(y);
}
template<typename A,typename B,typename C>inline void in(A&x,B&y,C&z) {
in(x);
in(y);
in(z);
}
template<typename A,typename B,typename C,typename D> inline void in(A&x,B&y,C&z,D&d) {
in(x);
in(y);
in(z);
in(d);
}
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
namespace SOLVE {
void main(){
}
}
signed main() {
#ifndef ONLINE_JUDGE
fr("/Users/zhangqingchuan/Desktop/cp/cp/input.txt");
fw("/Users/zhangqingchuan/Desktop/cp/cp/output.txt");
#endif
ll n,a,b;
in(n,a,b);
if(a>b)swap(a,b);
ll mi = a*(n-1)+b;
ll mx = b*(n-1)+a;
cout<<mx-mi+1;
SOLVE::main();
return 0;
}
Raw
B.cpp
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC optimize(3)
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC target("sse3","sse2","sse")
#pragma GCC target("avx","sse4","sse4.1","sse4.2","ssse3")
#pragma GCC target("f16c")
#pragma GCC optimize("inline","fast-math","unroll-loops","no-stack-protector")
#pragma GCC diagnostic error "-fwhole-program"
#pragma GCC diagnostic error "-fcse-skip-blocks"
#pragma GCC diagnostic error "-funsafe-loop-optimizations"
#pragma GCC diagnostic error "-std=c++14"
#include "bits/stdc++.h"
//#include "ext/pb_ds/tree_policy.hpp"
//#include "ext/pb_ds/assoc_container.hpp"
#define PB push_back
#define PF push_front
#define LB lower_bound
#define UB upper_bound
#define fr(x) freopen(x,"r",stdin)
#define fw(x) freopen(x,"w",stdout)
#define iout(x) printf("%d\n",x)
#define lout(x) printf("%lld\n",x)
#define REP(x,l,u) for(ll x = l;x<u;x++)
#define RREP(x,l,u) for(ll x = l;x>=u;x--)
#define complete_unique(a) a.erase(unique(a.begin(),a.end()),a.end())
#define mst(x,a) memset(x,a,sizeof(x))
#define all(a) a.begin(),a.end()
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define MP make_pair
#define sqr(x) ((x)*(x))
#define lowbit(x) ((x)&(-(x)))
#define lson (ind<<1)
#define rson (ind<<1|1)
#define se second
#define fi first
#define dbg(x) cerr<<#x<<" = "<<(x)<<endl;
#define sz(x) ((int)x.size())
#define EX0 exit(0);
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ld;
using namespace std;
typedef vector<ll> VLL;
typedef vector<int> VI;
const int block_size = 320;
typedef complex<ll> point;
const ll mod = 1e9+7;
const ll inf = 1e9+7;
const ld eps = 1e-9;
const db PI = atan(1)*4;
template<typename T>
inline int sign(const T&a) {
if(a<0)return -1;
if(a>0)return 1;
return 0;
}
template<typename T,typename S>inline bool upmin(T&a,const S&b){return a>b?a=b,1:0;}
template<typename T,typename S>inline bool upmax(T&a,const S&b){return a<b?a=b,1:0;}
template<typename T> inline void in(T &x) {
x = 0;
T f = 1;
char ch = getchar();
while (!isdigit(ch)) {
if (ch == '-') f = -1;
ch = getchar();
}
while (isdigit(ch)) {
x = x * 10 + ch - '0';
ch = getchar();
}
x *= f;
}
ll twop(int x) {
return 1LL<<x;
}
template<typename A,typename B > inline void in(A&x,B&y) {
in(x);
in(y);
}
template<typename A,typename B,typename C>inline void in(A&x,B&y,C&z) {
in(x);
in(y);
in(z);
}
template<typename A,typename B,typename C,typename D> inline void in(A&x,B&y,C&z,D&d) {
in(x);
in(y);
in(z);
in(d);
}
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
namespace SOLVE {
void main(){
}
}
pair<db, db> points[1010];
db test(int n){
REP(i,0,n)points[i] = MP( static_cast <float> (rand()) / static_cast <float> (RAND_MAX)
, static_cast <float> (rand()) / static_cast <float> (RAND_MAX));
db ans = 111;
REP(i,0,n){
REP(j,i+1,n){
ans = min(ans,sqrt(sqr(points[i].fi - points[j].fi) + sqr(points[i].se - points[j].se)));
}
}
return ans;
}
signed main() {
#ifndef ONLINE_JUDGE
fr("/Users/zhangqingchuan/Desktop/cp/cp/input.txt");
fw("/Users/zhangqingchuan/Desktop/cp/cp/output.txt");
#endif
ll n;in(n);
if(n > 1000)cout<<0.0001<<endl;
else{
const int cnt = 1e8/n/n;
db ans = 0;
REP(i,0,cnt)ans+=test(n);
cout<<setprecision(10)<<ans/cnt<<endl;
}
SOLVE::main();
return 0;
}
Raw
C.cpp
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC optimize(3)
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC target("sse3","sse2","sse")
#pragma GCC target("avx","sse4","sse4.1","sse4.2","ssse3")
#pragma GCC target("f16c")
#pragma GCC optimize("inline","fast-math","unroll-loops","no-stack-protector")
#pragma GCC diagnostic error "-fwhole-program"
#pragma GCC diagnostic error "-fcse-skip-blocks"
#pragma GCC diagnostic error "-funsafe-loop-optimizations"
#pragma GCC diagnostic error "-std=c++14"
#include "bits/stdc++.h"
//#include "ext/pb_ds/tree_policy.hpp"
//#include "ext/pb_ds/assoc_container.hpp"
#define PB push_back
#define PF push_front
#define LB lower_bound
#define UB upper_bound
#define fr(x) freopen(x,"r",stdin)
#define fw(x) freopen(x,"w",stdout)
#define iout(x) printf("%d\n",x)
#define lout(x) printf("%lld\n",x)
#define REP(x,l,u) for(ll x = l;x<u;x++)
#define RREP(x,l,u) for(ll x = l;x>=u;x--)
#define complete_unique(a) a.erase(unique(a.begin(),a.end()),a.end())
#define mst(x,a) memset(x,a,sizeof(x))
#define all(a) a.begin(),a.end()
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define MP make_pair
#define sqr(x) ((x)*(x))
#define lowbit(x) ((x)&(-(x)))
#define lson (ind<<1)
#define rson (ind<<1|1)
#define se second
#define fi first
#define dbg(x) cerr<<#x<<" = "<<(x)<<endl;
#define sz(x) ((int)x.size())
#define EX0 exit(0);
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ld;
using namespace std;
typedef vector<ll> VLL;
typedef vector<int> VI;
const int block_size = 320;
typedef complex<ll> point;
const ll mod = 1e9+7;
const ll inf = 1e9+7;
const ld eps = 1e-9;
const db PI = atan(1)*4;
template<typename T>
inline int sign(const T&a) {
if(a<0)return -1;
if(a>0)return 1;
return 0;
}
template<typename T,typename S>inline bool upmin(T&a,const S&b){return a>b?a=b,1:0;}
template<typename T,typename S>inline bool upmax(T&a,const S&b){return a<b?a=b,1:0;}
template<typename T> inline void in(T &x) {
x = 0;
T f = 1;
char ch = getchar();
while (!isdigit(ch)) {
if (ch == '-') f = -1;
ch = getchar();
}
while (isdigit(ch)) {
x = x * 10 + ch - '0';
ch = getchar();
}
x *= f;
}
ll twop(int x) {
return 1LL<<x;
}
template<typename A,typename B > inline void in(A&x,B&y) {
in(x);
in(y);
}
template<typename A,typename B,typename C>inline void in(A&x,B&y,C&z) {
in(x);
in(y);
in(z);
}
template<typename A,typename B,typename C,typename D> inline void in(A&x,B&y,C&z,D&d) {
in(x);
in(y);
in(z);
in(d);
}
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
namespace SOLVE {
void main(){
}
}
ll fast(ll a,ll b){
ll ans = 1;
while(b){
if(b&1){
b--;
ans = ans * a;
}else{
a = a * a;
b/=2;
}
}
return ans;
}
ll fast(ll a,ll b,ll mod){
ll ans = 1;
while(b){
if(b&1){
b--;
ans = ans * a % mod;
}else{
a = a * a % mod;
b/=2;
}
}
return ans%mod;
}
// m must be positive
template<typename T>
static T MOD(T a, T m)
{
a %= m;
if (a < 0)
a += m;
return a;
}
// a must be relatively prime to m
template<typename T>
static T inverse(T a, T m)
{
a = MOD(a, m);
if (a <= 1)
return a;
return MOD((1 - inverse(m, a) * m) / a, m);
}
const ll maxn = 2010;
ll fac[maxn],facinv[maxn],inv[maxn];
void init(){
fac[0] = 1;
REP(i,1,maxn)fac[i] = i*(fac[i-1])%mod;
facinv[maxn-1]=inverse(fac[maxn-1], mod);
RREP(i,maxn-2,0){
facinv[i] = facinv[i+1]*(i+1)%mod;
}
inv[1]=1;
for(int i=2;i<maxn;i++)
inv[i]=(mod-(ll)mod/i*inv[mod%i]%mod);
}
ll combi(int n,int m){
if(n<0 || m<0 || n<m)return 0;
return fac[n]*facinv[m]%mod*facinv[n-m]%mod;
}
string s;
ll ans[2010][100];
int cnt[100];
void pre(){
RREP(i,sz(s)-1,0){
REP(nxt,0,10){
if(cnt[nxt]){
REP(j,0,i+1){
ans[j][(s[i]-'0')*10+nxt] += cnt[nxt]*combi(i, j)%mod;
ans[j][(s[i]-'0')*10+nxt] %= mod;
}
}
}
cnt[s[i]-'0']++;
}
}
signed main() {
#ifndef ONLINE_JUDGE
fr("/Users/zhangqingchuan/Desktop/cp/cp/input.txt");
fw("/Users/zhangqingchuan/Desktop/cp/cp/output.txt");
#endif
init();
cin>>s;
pre();
int q;in(q);
while (q--) {
int len;
int a;
in(len,a);
if(len < 2){
puts("0");
continue;
}
len-=2;
if(len > sz(s))puts("0");
else{
lout(ans[len][a]);
}
}
SOLVE::main();
return 0;
}
Raw
D.cpp
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC optimize(3)
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC target("sse3","sse2","sse")
#pragma GCC target("avx","sse4","sse4.1","sse4.2","ssse3")
#pragma GCC target("f16c")
#pragma GCC optimize("inline","fast-math","unroll-loops","no-stack-protector")
#pragma GCC diagnostic error "-fwhole-program"
#pragma GCC diagnostic error "-fcse-skip-blocks"
#pragma GCC diagnostic error "-funsafe-loop-optimizations"
#pragma GCC diagnostic error "-std=c++14"
#include "bits/stdc++.h"
//#include "ext/pb_ds/tree_policy.hpp"
//#include "ext/pb_ds/assoc_container.hpp"
#define PB push_back
#define PF push_front
#define LB lower_bound
#define UB upper_bound
#define fr(x) freopen(x,"r",stdin)
#define fw(x) freopen(x,"w",stdout)
#define iout(x) printf("%d\n",x)
#define lout(x) printf("%lld\n",x)
#define REP(x,l,u) for(ll x = l;x<u;x++)
#define RREP(x,l,u) for(ll x = l;x>=u;x--)
#define complete_unique(a) a.erase(unique(a.begin(),a.end()),a.end())
#define mst(x,a) memset(x,a,sizeof(x))
#define all(a) a.begin(),a.end()
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define MP make_pair
#define sqr(x) ((x)*(x))
#define lowbit(x) ((x)&(-(x)))
#define lson (ind<<1)
#define rson (ind<<1|1)
#define se second
#define fi first
#define dbg(x) cerr<<#x<<" = "<<(x)<<endl;
#define sz(x) ((int)x.size())
#define EX0 exit(0);
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ld;
using namespace std;
typedef vector<ll> VLL;
typedef vector<int> VI;
const int block_size = 320;
typedef complex<ll> point;
const ll mod = 1e9+7;
const ll inf = 1e9+7;
const ld eps = 1e-9;
const db PI = atan(1)*4;
template<typename T>
inline int sign(const T&a) {
if(a<0)return -1;
if(a>0)return 1;
return 0;
}
template<typename T,typename S>inline bool upmin(T&a,const S&b){return a>b?a=b,1:0;}
template<typename T,typename S>inline bool upmax(T&a,const S&b){return a<b?a=b,1:0;}
template<typename T> inline void in(T &x) {
x = 0;
T f = 1;
char ch = getchar();
while (!isdigit(ch)) {
if (ch == '-') f = -1;
ch = getchar();
}
while (isdigit(ch)) {
x = x * 10 + ch - '0';
ch = getchar();
}
x *= f;
}
ll twop(int x) {
return 1LL<<x;
}
template<typename A,typename B > inline void in(A&x,B&y) {
in(x);
in(y);
}
template<typename A,typename B,typename C>inline void in(A&x,B&y,C&z) {
in(x);
in(y);
in(z);
}
template<typename A,typename B,typename C,typename D> inline void in(A&x,B&y,C&z,D&d) {
in(x);
in(y);
in(z);
in(d);
}
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
namespace SOLVE {
void main(){
}
}
map<int, int>mp;
vector<PLL>v;
int getSqrt(int x){
int tmp = sqrt(x);
tmp-=10;
upmax(tmp, 0);
while(tmp*tmp<x)tmp++;
if(tmp*tmp == x)return tmp;
else return -1;
}
bool small = 0;
signed main() {
#ifndef ONLINE_JUDGE
fr("/Users/zhangqingchuan/Desktop/cp/cp/input.txt");
fw("/Users/zhangqingchuan/Desktop/cp/cp/output.txt");
#endif
int n;
in(n);
REP(i,1,n+1){
PII a;
in(a.fi,a.se);
if(a.fi > a.se)swap(a.fi,a.se);
mp[a.fi]++;mp[a.se]++;
v.PB(a);
}
int l1,l2;
l1 = inf;
l2 = -1;
for(auto i:mp)upmin(l1, i.se);
for(auto i:mp)upmax(l2, i.se);
if(l1 == l2 && getSqrt(n) != -1 && l1 == getSqrt(n)*2){
cout<<getSqrt(n)<<" "<<getSqrt(n)<<endl;
for(auto i:mp)cout<<i.fi<<" ";
cout<<endl;
for(auto i:mp)cout<<i.fi<<" ";
cout<<endl;
return 0;
}
l2 = n/l1;
VI a,b;
for(auto i:mp){
if(i.se == l1+l2){
a.PB(i.fi);
b.PB(i.fi);
}
}
REP(i,0,1)
if(l1 == l2){
if(sz(a) == l1)break;
for(auto i:a)mp[i] = 0;
b = VI();
int min_value = -1;
for(auto i:mp){
if(i.se){
min_value = i.fi;break;
}
}
dbg(min_value);
sort(all(v));
for(auto i:v){
if(i.fi == min_value){
b.PB(i.se);
mp[i.se] = 0;
}
if(i.se == min_value){
b.PB(i.fi);
mp[i.fi] = 0;
}
}
for(auto i:mp){
if(i.se){
a.PB(i.fi);
}
}
}else{
for(auto i:mp){
if(i.se != l1+l2){
if(i.se == l1)b.PB(i.fi);
else a.PB(i.fi);
}
}
}
sort(all(a));
sort(all(b));
cout<<l1<<" "<<l2<<endl;
for(auto i:a)cout<<i<<" ";
cout<<endl;
for(auto i:b)cout<<i<<" ";
cout<<endl;
return 0;
}
Raw
E.cpp
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC optimize(3)
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC target("sse3","sse2","sse")
#pragma GCC target("avx","sse4","sse4.1","sse4.2","ssse3")
#pragma GCC target("f16c")
#pragma GCC optimize("inline","fast-math","unroll-loops","no-stack-protector")
#pragma GCC diagnostic error "-fwhole-program"
#pragma GCC diagnostic error "-fcse-skip-blocks"
#pragma GCC diagnostic error "-funsafe-loop-optimizations"
#pragma GCC diagnostic error "-std=c++14"
#include "bits/stdc++.h"
//#include "ext/pb_ds/tree_policy.hpp"
//#include "ext/pb_ds/assoc_container.hpp"
#define PB push_back
#define PF push_front
#define LB lower_bound
#define UB upper_bound
#define fr(x) freopen(x,"r",stdin)
#define fw(x) freopen(x,"w",stdout)
#define iout(x) printf("%d\n",x)
#define lout(x) printf("%lld\n",x)
#define REP(x,l,u) for(ll x = l;x<u;x++)
#define RREP(x,l,u) for(ll x = l;x>=u;x--)
#define complete_unique(a) a.erase(unique(a.begin(),a.end()),a.end())
#define mst(x,a) memset(x,a,sizeof(x))
#define all(a) a.begin(),a.end()
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define MP make_pair
#define sqr(x) ((x)*(x))
#define lowbit(x) ((x)&(-(x)))
#define lson (ind<<1)
#define rson (ind<<1|1)
#define se second
#define fi first
#define dbg(x) cerr<<#x<<" = "<<(x)<<endl;
#define sz(x) ((int)x.size())
#define EX0 exit(0);
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ld;
using namespace std;
typedef vector<ll> VLL;
typedef vector<int> VI;
const int block_size = 320;
typedef complex<ll> point;
const ll mod = 1e9+7;
const ll inf = 1e9+7;
const ld eps = 1e-9;
const db PI = atan(1)*4;
template<typename T>
inline int sign(const T&a) {
if(a<0)return -1;
if(a>0)return 1;
return 0;
}
template<typename T,typename S>inline bool upmin(T&a,const S&b){return a>b?a=b,1:0;}
template<typename T,typename S>inline bool upmax(T&a,const S&b){return a<b?a=b,1:0;}
template<typename T> inline void in(T &x) {
x = 0;
T f = 1;
char ch = getchar();
while (!isdigit(ch)) {
if (ch == '-') f = -1;
ch = getchar();
}
while (isdigit(ch)) {
x = x * 10 + ch - '0';
ch = getchar();
}
x *= f;
}
ll twop(int x) {
return 1LL<<x;
}
template<typename A,typename B > inline void in(A&x,B&y) {
in(x);
in(y);
}
template<typename A,typename B,typename C>inline void in(A&x,B&y,C&z) {
in(x);
in(y);
in(z);
}
template<typename A,typename B,typename C,typename D> inline void in(A&x,B&y,C&z,D&d) {
in(x);
in(y);
in(z);
in(d);
}
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
namespace SOLVE {
void main(){
}
}
const int maxn = 200010;
VI edge[maxn];
int sp[maxn],siz[maxn];
int n,k;
namespace INIT {
void dfs(int cur,int fa){
siz[cur] = 1;
for(auto e:edge[cur]){
if(e != fa){
dfs(e, cur);
siz[cur]+=siz[e];
}
}
}
}
namespace GAO {
int dp[maxn];
int mx;
int ok;
void dfs(int cur,int fa){
if(!ok)return;
dp[cur] = -1;
int mx_son = 0;
for(auto e:edge[cur]){
if(e != fa){
dfs(e, cur);
if(dp[e] < 0)dp[cur]+=dp[e];
upmax(mx_son, dp[e]);
}
}
if(sp[cur] && mx + dp[cur] < 0)ok = 0;
else{
if(sp[cur]){
dp[cur] += mx;
}else{
if(mx_son + dp[cur] >= 0)dp[cur] += mx_son;
}
}
}
bool check(int k){
mst(dp,0);
ok = 1;
mx = k;
dfs(1, 0);
return dp[1] >= 0 && ok;
}
void solve(){
int l = 1,r = n;
while(l<r){
int mid = (l+r)/2;
if(check(mid))r = mid;
else l = mid+1;
}
cout<<l<<endl;
}
}
signed main() {
#ifndef ONLINE_JUDGE
fr("/Users/zhangqingchuan/Desktop/cp/cp/input.txt");
fw("/Users/zhangqingchuan/Desktop/cp/cp/output.txt");
#endif
SOLVE::main();
in(n,k);
REP(i,1,n){
int a,b;in(a,b);
edge[a].PB(b);
edge[b].PB(a);
}
REP(i,1,k+1){
int c;in(c);
sp[c] = 1;
}
INIT::dfs(1, 0);
GAO::solve();
return 0;
}
Raw
F.cpp
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC optimize(3)
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC target("sse3","sse2","sse")
#pragma GCC target("avx","sse4","sse4.1","sse4.2","ssse3")
#pragma GCC target("f16c")
#pragma GCC optimize("inline","fast-math","unroll-loops","no-stack-protector")
#pragma GCC diagnostic error "-fwhole-program"
#pragma GCC diagnostic error "-fcse-skip-blocks"
#pragma GCC diagnostic error "-funsafe-loop-optimizations"
#pragma GCC diagnostic error "-std=c++14"
#include "bits/stdc++.h"
//#include "ext/pb_ds/tree_policy.hpp"
//#include "ext/pb_ds/assoc_container.hpp"
#define PB push_back
#define PF push_front
#define LB lower_bound
#define UB upper_bound
#define fr(x) freopen(x,"r",stdin)
#define fw(x) freopen(x,"w",stdout)
#define iout(x) printf("%d\n",x)
#define lout(x) printf("%lld\n",x)
#define REP(x,l,u) for(ll x = l;x<u;x++)
#define RREP(x,l,u) for(ll x = l;x>=u;x--)
#define complete_unique(a) a.erase(unique(a.begin(),a.end()),a.end())
#define mst(x,a) memset(x,a,sizeof(x))
#define all(a) a.begin(),a.end()
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define MP make_pair
#define sqr(x) ((x)*(x))
#define lowbit(x) ((x)&(-(x)))
#define lson (ind<<1)
#define rson (ind<<1|1)
#define se second
#define fi first
#define dbg(x) cerr<<#x<<" = "<<(x)<<endl;
#define sz(x) ((int)x.size())
#define EX0 exit(0);
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ld;
using namespace std;
typedef vector<ll> VLL;
typedef vector<int> VI;
const int block_size = 320;
typedef complex<ll> point;
const ll mod = 1e9+7;
const ll inf = 1e9+7;
const ld eps = 1e-9;
const db PI = atan(1)*4;
template<typename T>
inline int sign(const T&a) {
if(a<0)return -1;
if(a>0)return 1;
return 0;
}
template<typename T,typename S>inline bool upmin(T&a,const S&b){return a>b?a=b,1:0;}
template<typename T,typename S>inline bool upmax(T&a,const S&b){return a<b?a=b,1:0;}
template<typename T> inline void in(T &x) {
x = 0;
T f = 1;
char ch = getchar();
while (!isdigit(ch)) {
if (ch == '-') f = -1;
ch = getchar();
}
while (isdigit(ch)) {
x = x * 10 + ch - '0';
ch = getchar();
}
x *= f;
}
ll twop(int x) {
return 1LL<<x;
}
template<typename A,typename B > inline void in(A&x,B&y) {
in(x);
in(y);
}
template<typename A,typename B,typename C>inline void in(A&x,B&y,C&z) {
in(x);
in(y);
in(z);
}
template<typename A,typename B,typename C,typename D> inline void in(A&x,B&y,C&z,D&d) {
in(x);
in(y);
in(z);
in(d);
}
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
namespace SOLVE {
void main(){
}
}
ll ans = 0;
struct SAM {
static const int maxn = 300010 * 2;
struct node {
node*nxt[26],*fail;
int cnt;
int len;
};
node*root;
int cnt;
node no[maxn];
node*newnode() {
return &no[cnt++];
}
SAM() {
cnt = 0;
root = newnode();
}
void add(const string&s) {
node* cur = root;
REP(i,0,sz(s)) {
cur = add(cur, s[i]-'a');
}
}
node* add(node*p,int c) {
node*cur = newnode();
cur->len = p->len+1;
while(p &&!p->nxt[c])p->nxt[c] = cur,p = p->fail;
if(!p) {
cur->fail = root;
return cur;
}
node*q = p->nxt[c];
if(q->len == p->len+1) {
cur->fail = q;
} else {
node*nq = newnode();
*nq = *q;
nq->len = p->len+1;
q->fail = cur->fail = nq;
while(p&&p->nxt[c]==q)p->nxt[c] = nq,p = p->fail;
}
return cur;
}
void pre(const string&s) {
node* cur = root;
REP(i,0,sz(s)) {
cur = cur->nxt[s[i]-'a'];
cur->cnt++;
}
}
ll getCnt() {
vector<node*>v;
REP(i,1,cnt) {
v.PB(&no[i]);
}
sort(all(v),[](const node*a,const node*b) {
return a->len>b->len;
});
ll ans = 0;
REP(i, 0, sz(v)) {
v[i]->fail->cnt+=v[i]->cnt;
ans+=v[i]->cnt*(v[i]->len-v[i]->fail->len);
}
return ans;
}
ll getNumOfDistinctSubstrings() {
auto ans = 0;
REP(i,1,cnt)ans+=no[i].len-no[i].fail->len;
return (ans);
}
};
int n,q;
string s;
ll pre[1000010];
SAM sam;
ll dif[3000010];
signed main() {
#ifndef ONLINE_JUDGE
fr("/Users/zhangqingchuan/Desktop/cp/cp/input.txt");
fw("/Users/zhangqingchuan/Desktop/cp/cp/output.txt");
#endif
cin>>n>>q>>s;
SAM::node* cur = sam.root;
int len = 0;
REP(i,0,3*sz(s)){
cur = sam.add(cur, s[i%sz(s)]-'a');
ans += cur->len-cur->fail->len;
pre[++len] = ans;
}
REP(i,2*sz(s)+1,3*sz(s)+1){
dif[i] = pre[i]-pre[i-1];
dbg(dif[i]);
dif[i] += dif[i-1];
}
while (q--) {
ll c;
in(c);
if(c <=3*sz(s))
cout<<pre[c]<<endl;
else{
ll ans = pre[sz(s)*2];
ans += (c-2*sz(s))/sz(s)*dif[sz(s)*3];
ans += dif[(c%sz(s))+2*sz(s)];
cout<<ans<<endl;
}
}
SOLVE::main();
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment