Submission #591651

#	Time	Username	Problem	Language	Result	Execution time	Memory
591651		Iwanttobreakfree	Railway (BOI17_railway)	C++98	100 / 100	307 ms	39856 KiB

railway

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int cnt=0;
void dfs(int a,int par,vector<vector<int>>& g,vector<int>& t,vector<int>& li,vector<pair<int,int>>& pos,vector<vector<int>>& p,vector<int>& depth){
    p[a][0]=par;
    for(int i=1;i<19;i++)p[a][i]=p[p[a][i-1]][i-1];
    t[a]=li.size();
    pos[a].first=li.size();
    li.push_back(a);
    for(int x:g[a]){
        if(x==par)continue;
        depth[x]=depth[a]+1;
        dfs(x,a,g,t,li,pos,p,depth);
    }
    pos[a].second=li.size();
    li.push_back(a);
}
void r_upd(int n,int l,int r,vector<int>& t,vector<int>& la,int a,int b){
    //cout<<l<<' '<<r<<' '<<n<<'\n';
    if(b<a)return;
    if(a>r||b<l)return;
    if(a<=l&&r<=b){
        t[n]++;
        la[n]++;
    }else{
        int mid=(r+l)/2;
        if(la[n]){
            t[n<<1]+=la[n];
            la[n<<1]+=la[n];
            t[(n<<1)+1]+=la[n];
            la[(n<<1)+1]+=la[n];
            la[n]=0;
        }
        r_upd(n<<1,l,mid,t,la,a,b);
        r_upd((n<<1)+1,mid+1,r,t,la,a,b);
    }
}
int val(int n,int l,int r,vector<int>& t,vector<int>& la,int x){
    if(l>x||r<x)return 0;
    if(l==r&&l==x)return t[n];
    int mid=(r+l)/2;
    if(la[n]){
            t[n<<1]+=la[n];
            la[n<<1]+=la[n];
            t[(n<<1)+1]+=la[n];
            la[(n<<1)+1]+=la[n];
            la[n]=0;
        }
    int valls=val(n<<1,l,mid,t,la,x);
    int valrs=val((n<<1)+1,mid+1,r,t,la,x);
    return valls+valrs;
}
int bin_lift(int a,vector<vector<int>>& par,int dif){
    for(int i=0;i<19;i++){
        if(dif&(1<<i))a=par[a][i];
    }
    return a;
}
int LCA(int a,int b,vector<vector<int>>& par,vector<int>& depth){
    if(depth[a]>depth[b])swap(a,b);
    b=bin_lift(b,par,depth[b]-depth[a]);
    if(b==a)return a;
    for(int i=18;i>=0;i--){
        if(par[a][i]!=par[b][i]){
            a=par[a][i];
            b=par[b][i];
        }
    }
    return par[a][0];
}
int main(){
    int n,m,k,x,y,s;
    cin>>n>>m>>k;
    vector<vector<int>> g(n,vector<int>()),par(n,vector<int>(19));
    vector<pair<int,int>> edge(n-1),pos(n);
    vector<int> li,t(8*n),time(n),depth(n),la(8*n);
    // 132246655431
    for(int i=0;i<n-1;i++){
        cin>>x>>y;
        x--;y--;
        edge[i]={x,y};
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dfs(0,0,g,time,li,pos,par,depth);
    //for(int x:li)cout<<x+1<<' ';
    //cout<<endl;
    //for(int i=0;i<n;i++)cout<<i+1<<' '<<pos[i].first<<' '<<pos[i].second<<'\n';
    while(m--){
        cin>>s;
        vector<pair<int,int>> city(s);
        for(int i=0;i<s;i++){
            cin>>x;
            x--;
            city[i]={time[x],x};
            //cout<<time[x]<<' '<<x+1<<'\n';
        }
        sort(city.begin(),city.end());
        //for(auto x:city)cout<<x.second+1<<' ';
        int u=LCA(city[0].second,city[1].second,par,depth);
        //cout<<u<<' ';
        r_upd(1,0,2*n-1,t,la,pos[u].first+1,pos[city[0].second].first);
        r_upd(1,0,2*n-1,t,la,pos[u].first+1,pos[city[1].second].first);
        for(int i=2;i<s;i++){
            int v=LCA(city[i].second,city[i-1].second,par,depth);
            //cout<<v<<' ';
            r_upd(1,0,2*n-1,t,la,pos[v].first+1,pos[city[i].second].first);
            if(LCA(u,v,par,depth)==v){
                //cout<<i<<' ';
                r_upd(1,0,2*n-1,t,la,pos[v].first+1,pos[u].first);
                u=v;
            }
        }
        //break;
        //cout<<"ok ";
    }
    //for(int i=0;i<2*n;i++)cout<<val(1,0,2*n-1,t,la,i)<<' ';
    vector<int> ans;
    for(int i=0;i<edge.size();i++){
        if(depth[edge[i].first]<depth[edge[i].second]){
            int dif=val(1,0,2*n-1,t,la,pos[edge[i].second].first)-val(1,0,2*n-1,t,la,pos[edge[i].second].second);
            if(dif>=k)ans.push_back(i+1);
        }
        else{
            int dif=val(1,0,2*n-1,t,la,pos[edge[i].first].first)-val(1,0,2*n-1,t,la,pos[edge[i].first].second);
            if(dif>=k)ans.push_back(i+1);
        }
    }
    cout<<ans.size()<<'\n';
    for(int sol:ans)cout<<sol<<' ';
}

Compilation message (stderr)

railway.cpp: In function 'int main()':
railway.cpp:121:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |     for(int i=0;i<edge.size();i++){
      |                 ~^~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 15 / 15
• Subtask 3: 7 / 7
• Subtask 4: 29 / 29
• Subtask 5: 16 / 16
• Subtask 6: 25 / 25