Submission #1204192

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204192		8pete8	Tourism (JOI23_tourism)	C++20	100 / 100	763 ms	32184 KiB

tourism

#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<cassert>
#include<unordered_map>
#include <queue>
#include <cstdint>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric>
#include<bitset>
using namespace std;
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-lopps")
//#define int long long
using namespace std;
const int mod=1e9+7,mxn=1e5+5,inf=1e9,minf=-1e9,lg=17;
//#undef int
int n,k,m,q;
void setIO(string name){		
	ios_base::sync_with_stdio(0); cin.tie(0);		
	freopen((name+".in").c_str(),"r",stdin);		
	freopen((name+".out").c_str(),"w",stdout);	
}
vector<int>adj[mxn+10],adjO[mxn+10];
int C[mxn+10],ans[mxn+10],mark[mxn+10],cnt=0,bound,r,up[mxn+10][lg+1],h[mxn+10];
pii go[mxn+10];
int tin[mxn+10],tout[mxn+10],ct=0;
struct fen{
    int fwk[mxn+10];
    vector<pii>keep;
    void update(int pos,int val){
        keep.pb({pos,val});
        for(int i=pos;i<=m;i+=(i&-i))fwk[i]+=val;
    }
    int qry(int pos){
        int sum=0;
        for(int i=pos;i>0;i-=(i&-i))sum+=fwk[i];
        return sum;
    }
    void re(){
        for(auto i:keep)for(int j=i.f;j<=m;j+=(j&-j))fwk[j]-=i.s;
        keep.clear();
    }
}t;

void gettime(int cur,int p){
    tin[cur]=++ct;
    for(auto i:adjO[cur])if(i!=p){
        up[i][0]=cur;
        h[i]=h[cur]+1;
        gettime(i,cur);
    }
    tout[cur]=ct;
}
int lca(int a,int b){
    if(h[a]<h[b])swap(a,b);
    int k=h[a]-h[b];
    for(int i=0;i<=lg;i++)if(k&(1LL<<i))a=up[a][i];
    if(a==b)return a;
    for(int i=lg;i>=0;i--)if(up[a][i]!=up[b][i]){
        a=up[a][i],b=up[b][i];
    }
    return up[a][0];
}

void dfsweak(int cur,int id){
    if(mark[cur])return;
    mark[cur]=id;
    t.update(id,go[cur].s+1);
    if(cur==C[bound])return;
    if(!mark[go[cur].f]){
        dfsweak(go[cur].f,id);
    }
}
void dfsstrong(int cur,int id){
    if(mark[cur]>=bound)return;
    if(mark[cur])t.update(mark[cur],-go[cur].s-1);
    mark[cur]=id;
    cnt+=go[cur].s+1;
    if(cur==C[bound])return;
    if(!mark[go[cur].f]||(mark[go[cur].f]<bound)){
        dfsstrong(go[cur].f,id);
    }
}
void dfsfind(int cur,int p){
    for(auto i:adj[cur])if(i!=p){
        go[i]={cur,abs(h[cur]-h[i])-1};
        dfsfind(i,cur);
    }
}
bool cmp2(pair<pii,int>a,pair<pii,int>b){
    return a.f.s<b.f.s;
}
int same[mxn+10];
void con(int a,int b){
    if(a==b)return;
    adj[a].pb(b);
    adj[b].pb(a);
}
void dnc(int l,int r,vector<pair<pii,int>>qry){
    int mid=l+(r-l)/2;
    if(l==r){
        for(auto i:qry)ans[i.s]=1;
        return;
    }
    bound=mid+1;
    //build virtual tree
    vector<pii>have;
    for(int i=l;i<=r;i++){
        if(!same[C[i]])have.pb({tin[C[i]],C[i]});
        same[C[i]]=1;
    }
    sort(all(have));
    for(int i=1;i<have.size();i++){
        int x=lca(have[i-1].s,have[i].s);
        if(!same[x])have.pb({tin[x],x});
        same[x]=1;
    }
    sort(all(have));
	for(int i=1;i<have.size();i++)con(lca(have[i-1].s,have[i].s),have[i].s);
    //precomp
    cnt=0;
    dfsfind(C[bound],-1);
    go[C[bound]].s=0;
    for(int i=mid;i>=l;i--)dfsweak(C[i],i);
    sort(all(qry),cmp2);
    vector<pair<pii,int>>L,R;
    int cur=bound+1;
    for(auto i:qry){
        if(i.f.f<=mid&&i.f.s>mid){
            while(cur<=i.f.s){
                dfsstrong(C[cur],cur);
                cur++;
            }
            ans[i.s]=cnt+t.qry(mid)-t.qry(i.f.f-1);
        }
        else if(i.f.s<=mid)L.pb(i);
        else R.pb(i);
    }
    for(auto i:have)adj[i.s].clear(),same[i.s]=mark[i.s]=0;
    t.re();
    dnc(l,mid,L);
    dnc(mid+1,r,R);
}
int32_t main(){
    fastio
    cin>>n>>m>>q;
    for(int i=1;i<=n-1;i++){
        int a,b;cin>>a>>b;
        adjO[a].pb(b);
        adjO[b].pb(a);
    }
    gettime(1,-1);
    for(int i=0;i<=lg;i++)up[1][i]=1;
    for(int j=1;j<=lg;j++)for(int i=1;i<=n;i++){
        up[i][j]=up[up[i][j-1]][j-1];
    }
    for(int i=1;i<=m;i++)cin>>C[i];
    vector<pair<pii,int>>qry;
    for(int i=0;i<q;i++){
        int l,r;cin>>l>>r;
        qry.pb({{l,r,},i});
    }
    dnc(1,m,qry);
    for(int i=0;i<q;i++)cout<<ans[i]<<'\n';
}
/*
dnc??

let weak mark = id of node from [L,mid] that passed through edge i
strong mark =  id of node from [mid+1,R]

then for each l=mid->L we insert l (dfs toward mid+1)
when discover weak or strong marks we break
and keep sum of edge with weak marks = i (i is in [L,mid])
then sweep line r=mid+2->R inserting r (dfs toward mid+1)
when discover weak mark overwrite the mark and update answer
else if its strong break

to answer qry ql,qr where ql<=mid and qr>mid
just add sum of [ql,mid] when we sweep to qr

then will be n^2 ? because each layer still takes O(n) to dfs

build virtual tree so the dfs is O(2*(r-l+1))?

can we use MO's?
*/

Compilation message (stderr)

tourism.cpp:32:40: warning: bad option '-funroll-lopps' to pragma 'optimize' [-Wpragmas]
   32 | #pragma GCC optimize ("03,unroll-lopps")
      |                                        ^
tourism.cpp:38:23: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   38 | void setIO(string name){
      |                       ^
tourism.cpp:50:32: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   50 |     void update(int pos,int val){
      |                                ^
tourism.cpp:54:20: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   54 |     int qry(int pos){
      |                    ^
tourism.cpp:59:13: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   59 |     void re(){
      |             ^
tourism.cpp:65:27: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   65 | void gettime(int cur,int p){
      |                           ^
tourism.cpp:74:20: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   74 | int lca(int a,int b){
      |                    ^
tourism.cpp:85:28: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   85 | void dfsweak(int cur,int id){
      |                            ^
tourism.cpp:94:30: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   94 | void dfsstrong(int cur,int id){
      |                              ^
tourism.cpp:104:27: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  104 | void dfsfind(int cur,int p){
      |                           ^
tourism.cpp:110:40: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  110 | bool cmp2(pair<pii,int>a,pair<pii,int>b){
      |                                        ^
tourism.cpp:114:21: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  114 | void con(int a,int b){
      |                     ^
tourism.cpp:119:46: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  119 | void dnc(int l,int r,vector<pair<pii,int>>qry){
      |                                              ^
tourism.cpp:164:14: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  164 | int32_t main(){
      |              ^
tourism.cpp: In function 'void setIO(std::string)':
tourism.cpp:40:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |         freopen((name+".in").c_str(),"r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
tourism.cpp:41:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |         freopen((name+".out").c_str(),"w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 7 / 7
• Subtask 4: 18 / 18
• Subtask 5: 24 / 24
• Subtask 6: 41 / 41