Submission #253803

#	Time	Username	Problem	Language	Result	Execution time	Memory
253803		test2	Railway (BOI17_railway)	C++14	8 / 100	1103 ms	466736 KiB

railway

#include<bits/stdc++.h>

using namespace std ; 

const int N = (1 << 15) ; 

int  n , m , k ; 
int st[N] , en[N] ; 
vector<int>  deps[N ] , ans ;
int t  = 3; 
int L[N] , R[N] ;
vector<pair<int , int > >  adj[N] ;

//////



long long f(long long x, long long y)
{
        return x + y ; 
}

struct node
{

        long long sum = 0;

        node *l, *r;

        node(long long _sum) : sum(_sum), l(nullptr), r(nullptr)
        {
        }

        node(node *_l, node *_r) : l(_l), r(_r), sum(0)
        {
                if (l)
                        sum = f(sum, l->sum);
                if (r)
                        sum = f(sum, r->sum);
        }
};

node *update(node *nod, int L, int R, int idx, long long val)
{

        if (L == R)
        {
                nod->sum = f(val , nod -> sum ) ; 
                return nod;
        }

        int mid = (L + R) >> 1;

        if (idx <= mid)
        {
                if (nod->l == NULL)
                {
                        nod->l = new node(0);
                }
                return new node(update(nod->l, L, mid, idx, val), nod->r);
        }
        else
        {
                if (nod->r == NULL)
                {
                        nod->r = new node(0);
                }
                return new node(nod->l, update(nod->r, mid + 1, R, idx, val));
        }
}

long long query(node *nod, int L, int R, int l, int r)
{
        if (l > r || l > R || r < L || nod == NULL)
                return 0;
        if (L >= l && R <= r)
        {
                return nod->sum;
        }

        int mid = (L + R) >> 1;

        long long s1 = query(nod->l, L, mid, l, r);
        long long s2 = query(nod->r, mid + 1, R, l, r);

        return f(s1, s2);
}

struct node2
{

        node *sum = new node(0);

        node2 *l, *r;

        node2() : l(nullptr), r(nullptr)
        {
        }

        node2(node2 *_l, node2 *_r) : l(_l), r(_r)
        {
        }
};

long long query2(node2 *nod, int L, int R, int l, int r, int x, int y)
{

        if (l > R || r < L || l > r || nod == NULL)
                return 0;

        if (L >= l && R <= r)
        {
                return query(nod->sum, 1, N, x, y);
        }

        int mid = (L + R) >> 1;

        long long s1 = query2(nod->l, L, mid, l, r, x, y);
        long long s2 = query2(nod->r, mid + 1, R, l, r, x, y);

        return f(s1, s2);
}

void upd(node2 *nod, int L, int R, int x, int y, long long z)
{

        if (L == R)
        {
                nod->sum = update(nod->sum, 1, N, y, z);
                return;
        }

        int mid = (L + R) >> 1;
        long long add = 0;
        if (x <= mid)
        {
                if (nod->l == NULL)
                {
                        nod->l = new node2();
                }
                upd(nod->l, L, mid, x, y, z);
        }
        else
        {
                if (nod->r == NULL)
                {
                        nod->r = new node2();
                }
                upd(nod->r, mid + 1, R, x, y, z);
        }

        nod->sum = update(nod->sum, 1, N, y, z );
        return;
}

node2 *root = new node2() ; 
node2 *root2 = new node2() ; 


/////




void dfz(int x , int p){
        st[x] = ++ t; 
        for(auto u : adj[x]){
                if( u.first == p)
                        continue ; 
                dfz(u.first ,x ) ; 
        }
        en[x] = ++t ; 
        return ;
}

vector<pair<int , int > > vs ; 

void dfs(int x , int p){

        for(auto u: adj[x]){
                if(u.first == p)
                        continue ;
                int cnt = m ; 

                cnt -= query2(root , 1 , N , 1 , st[u.first] , en[u.first] , N ) ; 
                cnt -= query2(root2 , 1 , N , st[u.first] , N , 1 , en[u.first] ) ; 

                if(cnt>= k){
                        ans.push_back(u.second + 1) ;
                }
                dfs(u .first, x) ;
        }
        return ;
}

int main(){


        ios_base::sync_with_stdio(0) ; 
        cin.tie(0) ; 
        //freopen("in.in" , "r" , stdin) ; 

        cin >> n >> m >> k ; 

        for(int i = 0 ; i < n-1 ;i ++){
                int u , v; 
                cin >> u >> v; 
                adj[u].push_back({v , i }) ; 
                adj[v].push_back({u , i}) ;

        }

        dfz(1 , 1) ;


        for(int i = 0 ;i < m ;i++){
                int x ; cin >> x ;
                vector<int> vec ; 
                for(int j = 0 ;j < x ;j++){
                        int t ; cin >> t ; 
                        deps[i].push_back(t) ;
                        vec.push_back(st[t]) ;
                }
                sort(vec.begin() , vec.end()) ;         
                int l = 1 ; 

                for(auto u: vec){
                        if(u > l  && l+1 <= u-1  ){
                                vs.push_back({l +1 , u -1 }) ;
                                upd(root ,1 , N , l+1 , u - 1 , 1) ;
                        }
                        l = u ; 
                }
                L[i] = vec[0] ; 
                R[i] = vec.back() ;
                upd(root2 ,1 , N , L[i] , R[i] , 1) ; 
                vs.push_back({l+1 , N -1}) ;
                upd(root , 1 , N , l+1 , N-1 , 1) ; 
        }
        dfs( 1, 1) ;

        cout<< (int) ans.size() <<"\n" ;
        sort(ans.begin() , ans.end()) ;
        for(auto u : ans){
                cout<< u <<" " ;
        }

        return 0 ;
}

Compilation message (stderr)

railway.cpp: In constructor 'node::node(node*, node*)':
railway.cpp:28:19: warning: 'node::r' will be initialized after [-Wreorder]
         node *l, *r;
                   ^
railway.cpp:26:25: warning:   'long long int node::sum' [-Wreorder]
         long long sum = 0;
                         ^
railway.cpp:34:9: warning:   when initialized here [-Wreorder]
         node(node *_l, node *_r) : l(_l), r(_r), sum(0)
         ^~~~
railway.cpp: In function 'void upd(node2*, int, int, int, int, long long int)':
railway.cpp:134:19: warning: unused variable 'add' [-Wunused-variable]
         long long add = 0;
                   ^~~

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