大问题
为什么主流评测网站上用 c++14 -O2 交的代码中，正常的应该为 int main()，但是把 int 删去后也能得一样的分。
例： P3979 遥远的国度
正常：
#include<bits/stdc++.h>
#define ll long long
#define Maxn 100005
using namespace std;
ll read(){
ll ret=0, sgn=0, ch=getchar();
while(!isdigit(ch)){ sgn|=( ch=='-'), ch=getchar(); }
while(isdigit(ch)){ ret=ret*10+ch-'0', ch=getchar(); }
return !sgn ? ret : -ret;
}
ll n, m, a, b, val[Maxn], root=-1;
ll dfn[Maxn], dfncnt=0, rnk[Maxn];
ll son[Maxn], fa[Maxn][35], top[Maxn];
ll dep[Maxn], siz[Maxn];
vector<ll> v[Maxn];
ll opt, x, y, Value, id, num;
ll Min(ll a, ll b){
return a>b ? b : a;
}
void dfs1(ll x){
siz[x]=1, son[x]=-1;
for(ll i=0;i<(ll)v[x].size();i++){
ll tmp=v[x][i];
if(!dep[tmp]){
dep[tmp]=dep[x]+1, fa[tmp][0]=x;
dfs1(tmp), siz[x]+=siz[tmp];
son[x]=((!son[x] || siz[son[x]]<siz[tmp]) ? tmp : son[x]);
}
}
} // son, dep, fa, siz
void dfs2(ll x, ll Top){
top[x]=Top;
dfn[x]=++dfncnt, rnk[dfn[x]]=x;
if(son[x]==-1){ return ; }
dfs2(son[x], Top);
for(ll i=0;i<(ll)v[x].size();i++){
ll tmp=v[x][i];
if(tmp!=fa[x][0] && tmp!=son[x]){
dfs2(tmp, tmp);
}
}
} // dfn, rnk, top
struct Seg_tree{
#define lid (id<<1)
#define rid (id<<1|1)
struct seg_tree{
ll l, r, minl, lazy;
} tr[Maxn<<2];
void build(ll id, ll l, ll r){
tr[id].l=l, tr[id].r=r;
if(l==r){
tr[id].lazy=0, tr[id].minl=val[rnk[l]];
return ;
}
ll mid=(l+r)>>1;
build(lid, l, mid), build(rid, mid+1, r);
tr[id].lazy=0, tr[id].minl=Min(tr[lid].minl, tr[rid].minl);
}
void pushdown(ll id){
if(tr[id].l!=tr[id].r && tr[id].lazy){
tr[lid].lazy=tr[rid].lazy=tr[id].lazy;
tr[lid].minl=tr[rid].minl=tr[id].lazy;
tr[id].lazy=0;
}
}
void change(ll id, ll l, ll r, ll tov){
pushdown(id);
if(tr[id].l==l && tr[id].r==r){
tr[id].lazy=tr[id].minl=tov;
return ;
}
ll mid=(tr[id].l+tr[id].r)>>1;
if(r<=mid){ change(lid, l, r, tov); }
else if(l>mid){ change(rid, l, r, tov); }
else{ change(lid, l, mid, tov), change(rid, mid+1, r, tov); }
tr[id].minl=Min(tr[lid].minl, tr[rid].minl);
}
ll query(ll id, ll l, ll r){
if(l>r){ return 9223372036854775807; }
pushdown(id);
if(tr[id].l==l && tr[id].r==r){
return tr[id].minl;
}
ll mid=(tr[id].l+tr[id].r)>>1;
if(r<=mid){ return query(lid, l, r); }
else if(l>mid){ return query(rid, l, r); }
else{ return Min(query(lid, l, mid), query(rid, mid+1, r)); }
}
} sg;
void Change(ll x, ll y, ll v){
while(top[x]!=top[y]){
if(dep[top[x]]>dep[top[y]]){ x^=y, y^=x, x^=y; }
sg.change(1, dfn[top[y]], dfn[y], v);
y=fa[top[y]][0];
}
if(dep[x]>dep[y]){ x^=y, y^=x, x^=y; }
sg.change(1, dfn[x], dfn[y], v);
}
ll LCA(ll x, ll y){
while(top[x]!=top[y]){
if(dep[top[x]]>dep[top[y]]){
x=fa[top[x]][0];
} else{
y=fa[top[y]][0];
}
}
return (dep[x]>dep[y] ? y : x);
}
int main() // this this this this this this this this this this this this this this this this this this this
{
n=read(), m=read();
for(ll i=1;i<n;i++){
a=read(), b=read();
v[a].push_back(b);
v[b].push_back(a);
} for(ll i=1;i<=n;i++){
cin>>val[i];
} cin>>root;
dep[1]=1, fa[1][0]=0;
dfs1(1), dfs2(1, 1);
sg.build(1, 1, n);
for(ll i=1;i<=20;i++){
for(ll j=1;j<=n;j++){
fa[j][i]=fa[fa[j][i-1]][i-1];
}
}
for(ll i=1;i<=m;i++){
opt=read();
if(opt==1){
root=read();
} else if(opt==2){
x=read(), y=read(), Value=read();
Change(x, y, Value);
} else{
id=read();
if(root==id){
printf("%lld\n", sg.query(1, 1, n));
} else if(dep[LCA(id, root)]<dep[id]){
printf("%lld\n", sg.query(1, dfn[id], dfn[id]+siz[id]-1));
} else{
num=root;
for(ll i=20;i>=0;i--){
if(dep[fa[num][i]]>dep[id]){
num=fa[num][i];
}
}
// ll a1=sg.query(1, 1, dfn[num]-1);
// puts("hjghfads");
// cout<<dfn[num]<<" "<<siz[num]<<" "<<n<<endl;
// ll a2=sg.query(1, dfn[num]+siz[num], n);
// puts("jgadfkjfgjhgfhfdsg");
printf("%lld\n", Min(sg.query(1, 1, dfn[num]-1), sg.query(1, dfn[num]+siz[num], n)));
}
}
}
return 0;
}
删去：
#include<bits/stdc++.h>
#define ll long long
#define Maxn 100005
using namespace std;
ll read(){
ll ret=0, sgn=0, ch=getchar();
while(!isdigit(ch)){ sgn|=( ch=='-'), ch=getchar(); }
while(isdigit(ch)){ ret=ret*10+ch-'0', ch=getchar(); }
return !sgn ? ret : -ret;
}
ll n, m, a, b, val[Maxn], root=-1;
ll dfn[Maxn], dfncnt=0, rnk[Maxn];
ll son[Maxn], fa[Maxn][35], top[Maxn];
ll dep[Maxn], siz[Maxn];
vector<ll> v[Maxn];
ll opt, x, y, Value, id, num;
ll Min(ll a, ll b){
return a>b ? b : a;
}
void dfs1(ll x){
siz[x]=1, son[x]=-1;
for(ll i=0;i<(ll)v[x].size();i++){
ll tmp=v[x][i];
if(!dep[tmp]){
dep[tmp]=dep[x]+1, fa[tmp][0]=x;
dfs1(tmp), siz[x]+=siz[tmp];
son[x]=((!son[x] || siz[son[x]]<siz[tmp]) ? tmp : son[x]);
}
}
} // son, dep, fa, siz
void dfs2(ll x, ll Top){
top[x]=Top;
dfn[x]=++dfncnt, rnk[dfn[x]]=x;
if(son[x]==-1){ return ; }
dfs2(son[x], Top);
for(ll i=0;i<(ll)v[x].size();i++){
ll tmp=v[x][i];
if(tmp!=fa[x][0] && tmp!=son[x]){
dfs2(tmp, tmp);
}
}
} // dfn, rnk, top
struct Seg_tree{
#define lid (id<<1)
#define rid (id<<1|1)
struct seg_tree{
ll l, r, minl, lazy;
} tr[Maxn<<2];
void build(ll id, ll l, ll r){
tr[id].l=l, tr[id].r=r;
if(l==r){
tr[id].lazy=0, tr[id].minl=val[rnk[l]];
return ;
}
ll mid=(l+r)>>1;
build(lid, l, mid), build(rid, mid+1, r);
tr[id].lazy=0, tr[id].minl=Min(tr[lid].minl, tr[rid].minl);
}
void pushdown(ll id){
if(tr[id].l!=tr[id].r && tr[id].lazy){
tr[lid].lazy=tr[rid].lazy=tr[id].lazy;
tr[lid].minl=tr[rid].minl=tr[id].lazy;
tr[id].lazy=0;
}
}
void change(ll id, ll l, ll r, ll tov){
pushdown(id);
if(tr[id].l==l && tr[id].r==r){
tr[id].lazy=tr[id].minl=tov;
return ;
}
ll mid=(tr[id].l+tr[id].r)>>1;
if(r<=mid){ change(lid, l, r, tov); }
else if(l>mid){ change(rid, l, r, tov); }
else{ change(lid, l, mid, tov), change(rid, mid+1, r, tov); }
tr[id].minl=Min(tr[lid].minl, tr[rid].minl);
}
ll query(ll id, ll l, ll r){
if(l>r){ return 9223372036854775807; }
pushdown(id);
if(tr[id].l==l && tr[id].r==r){
return tr[id].minl;
}
ll mid=(tr[id].l+tr[id].r)>>1;
if(r<=mid){ return query(lid, l, r); }
else if(l>mid){ return query(rid, l, r); }
else{ return Min(query(lid, l, mid), query(rid, mid+1, r)); }
}
} sg;
void Change(ll x, ll y, ll v){
while(top[x]!=top[y]){
if(dep[top[x]]>dep[top[y]]){ x^=y, y^=x, x^=y; }
sg.change(1, dfn[top[y]], dfn[y], v);
y=fa[top[y]][0];
}
if(dep[x]>dep[y]){ x^=y, y^=x, x^=y; }
sg.change(1, dfn[x], dfn[y], v);
}
ll LCA(ll x, ll y){
while(top[x]!=top[y]){
if(dep[top[x]]>dep[top[y]]){
x=fa[top[x]][0];
} else{
y=fa[top[y]][0];
}
}
return (dep[x]>dep[y] ? y : x);
}
main() // this this this this this this this this this this this this this this this this this this this
{
n=read(), m=read();
for(ll i=1;i<n;i++){
a=read(), b=read();
v[a].push_back(b);
v[b].push_back(a);
} for(ll i=1;i<=n;i++){
cin>>val[i];
} cin>>root;
dep[1]=1, fa[1][0]=0;
dfs1(1), dfs2(1, 1);
sg.build(1, 1, n);
for(ll i=1;i<=20;i++){
for(ll j=1;j<=n;j++){
fa[j][i]=fa[fa[j][i-1]][i-1];
}
}
for(ll i=1;i<=m;i++){
opt=read();
if(opt==1){
root=read();
} else if(opt==2){
x=read(), y=read(), Value=read();
Change(x, y, Value);
} else{
id=read();
if(root==id){
printf("%lld\n", sg.query(1, 1, n));
} else if(dep[LCA(id, root)]<dep[id]){
printf("%lld\n", sg.query(1, dfn[id], dfn[id]+siz[id]-1));
} else{
num=root;
for(ll i=20;i>=0;i--){
if(dep[fa[num][i]]>dep[id]){
num=fa[num][i];
}
}
// ll a1=sg.query(1, 1, dfn[num]-1);
// puts("hjghfads");
// cout<<dfn[num]<<" "<<siz[num]<<" "<<n<<endl;
// ll a2=sg.query(1, dfn[num]+siz[num], n);
// puts("jgadfkjfgjhgfhfdsg");
printf("%lld\n", Min(sg.query(1, 1, dfn[num]-1), sg.query(1, dfn[num]+siz[num], n)));
}
}
}
return 0;
}
两者都是 100 pts 。
WHY???
加载中...