Submission #212231

#	Time	Username	Problem	Language	Result	Execution time	Memory
212231		Ruxandra985	Traffickers (RMI18_traffickers)	C++14	100 / 100	981 ms	258552 KiB

traffickers

#include <bits/stdc++.h>
#define DIMN 100010
using namespace std;
int tt[DIMN] , lvl[DIMN] , f[DIMN];
int up[DIMN] , l[DIMN] , d[DIMN] , poz[DIMN];
struct idk{
    idk *st , *dr;
    short mp[2100];
    idk(){
        st = dr = 0;
        memset (mp , 0 , sizeof(mp));
    }
};
idk *aint[DIMN];
vector <int> v[DIMN] , w[DIMN];
int elem , lnt , curr;
void dfs_lant(int nod , int fth){
    int i,vecin,ok=0,maxi,fiu;
    tt[nod] = fth;
    d[nod] = 1;
    maxi=0;
    fiu=0;
    for (i=0;i<v[nod].size();++i){
        vecin=v[nod][i];
        if (vecin!=fth){
            ok=1;
            lvl[vecin] = 1 + lvl[nod];
            dfs_lant(vecin , nod);
            d[nod] += d[vecin];
            if (d[vecin]>maxi){
                maxi=d[vecin];
                fiu=vecin;
            }
        }
    }
    if (!ok){ /// frunza
        lnt++;
        l[nod]=lnt; /// lantul din care apartine
        w[lnt].push_back(nod);
    }else { /// unim cu poz
        w[l[fiu]].push_back(nod);
        l[nod]=l[fiu];
        for (i=0;i<v[nod].size();++i){
            vecin=v[nod][i];
            if (vecin!=fth && vecin!=fiu)
                up[l[vecin]]=nod; /// din lantul vecinului trecem in lantul nodului
        }
    }
    v[nod].clear();
}
void update_aint (idk *&node , int st , int dr , int l , int r , int len , int val , int sens){
    int mid , rest;
    if (st == dr){
        //if (st == 1 || st == 0)
          //  printf ("a");
        //if (len == 1)
          //  printf ("a");
        node->mp[len * 100 + curr] += val;
        curr++;
        return;
    }
    mid=((st+dr)>>1);
    if (sens == -1){
        if (l <= mid){
            if (node->st == NULL){
                node->st = new idk;
            }
            update_aint(node->st , st , mid , l , r , len , val , sens);
        }
        if (mid + 1 <= r){
            if (node->dr == NULL){
                node->dr = new idk;
            }
            update_aint(node->dr , mid + 1 , dr , l , r , len , val , sens);
        }
    }
    else {
        if (mid + 1 <= r){
            if (node->dr == NULL){
                node->dr = new idk;
            }
            update_aint(node->dr , mid + 1 , dr , l , r , len , val , sens);
        }
        if (l <= mid){
            if (node->st == NULL){
                node->st = new idk;
            }
            update_aint(node->st , st , mid , l , r , len , val , sens);
        }
    }

    for (rest = 0 ; rest < len ; ++rest)
        node->mp[len * 100 + rest] = 0;

    if (node->st != NULL)
        for (rest = 0 ; rest < len ; ++rest)
            node->mp[len * 100 + rest] += node->st->mp[len * 100 + rest];

    if (node->dr != NULL)
        for (rest = 0 ; rest < len ; ++rest)
            node->mp[len * 100 + rest] += node->dr->mp[len * 100 + rest];
    //if (len == 1 && l == 20)
      //  printf ("%d %d %d\n",node->mp[100] , st , dr);
}
void update (int x , int y , int len , int val){
    if (l[x]!=l[y]){ /// avansam
        if (lvl[up[l[x]]]>lvl[up[l[y]]]){
            update_aint (aint[l[x]] , 0 , w[l[x]].size()-1 , 0 , poz[x] , len , val , 1);
            update ( up[l[x]] , y , len , val);
        }
        else{
            update ( x , up[l[y]] , len , val );

            update_aint( aint[l[y]] , 0 , w[l[y]].size()-1 , 0 , poz[y] , len , val , -1 );
        }
    }
    else {
        if (poz[x] <= poz[y])
            update_aint( aint[l[x]] , 0 , w[l[x]].size()-1 , poz[x] , poz[y] , len , val , -1 );
        else
            update_aint( aint[l[x]] , 0 , w[l[x]].size()-1 , poz[y] , poz[x] , len , val , 1 );
    }
}
long long query_aint (idk *&node , int st , int dr , int px , int py , int t1 , int t2){
    int mid , len , rest;
    long long sol = 0;
    if (px <= st && dr <= py){
        for (len = 1 ; len <= 20 ; ++len){
            for (rest = 0 ; rest < len ; ++rest){
                sol += 1LL * node->mp[len * 100 + rest] * ((t2 / len) + (t2 % len >= rest) - ((t1 - 1) / len) - ((t1 - 1) % len >= rest));
            }
        }

        return sol;
    }
    mid = ((st + dr)>>1);
    if (px <= mid && node->st != NULL)
        sol = sol + query_aint(node->st , st , mid , px , py , t1 , t2);
    if (mid+1 <= py && node->dr != NULL)
        sol = sol + query_aint(node->dr , mid + 1 , dr , px , py , t1 , t2);
    return sol;
}
long long query (int x , int y , int t1 , int t2){
    if (l[x] != l[y]){ /// avansam
        if (lvl[up[l[x]]]>lvl[up[l[y]]])
            return query(up[l[x]] , y , t1 , t2) + query_aint(aint[l[x]] , 0 , w[l[x]].size()-1 , 0 , poz[x] , t1 , t2);
        else{
            //printf ("%d",query_aint(aint[l[y]] , 0 , w[l[y]].size()-1 , 0 , poz[y] , t1 , t2));
            return query(x , up[l[y]] , t1 , t2) + query_aint(aint[l[y]] , 0 , w[l[y]].size()-1 , 0 , poz[y] , t1 , t2);
        }
    }
    else{
        return query_aint(aint[l[x]] , 0 , w[l[x]].size()-1 , min(poz[x],poz[y]) , max(poz[x],poz[y]) , t1 , t2);
    }
}
int adauga (int x , int y){
    int nod1 , nod2;
    nod1 = x;
    nod2 = y;

    while (lvl[nod1] > lvl[nod2])
        nod1 = tt[nod1];

    while (lvl[nod1] < lvl[nod2])
        nod2 = tt[nod2];

    while (nod1 != nod2){
        nod1 = tt[nod1];
        nod2 = tt[nod2];
    }


    return lvl[x] + lvl[y] - 2 * lvl[nod1] + 1;
}
int main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    int n , i , x , y , tip , k , q , t1 , t2 , p , vecin , len;
    fscanf (fin,"%d",&n);
    for (i = 1 ; i < n ; ++i){
        fscanf (fin,"%d%d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
    }

    lvl[1] = 1;
    dfs_lant(1 , 0);

    /// fiecare nod al catelea e
    for (i=1;i<=lnt;++i){
        reverse(w[i].begin(),w[i].end());
        p=0;
        for (vector <int> :: iterator j=w[i].begin();j!=w[i].end();j++){
            /// pozitia lui din lantul curent
            vecin=*j;
            poz[vecin]=p;
            p++;
        }
        aint[i] = new idk;
    }


    fscanf (fin,"%d",&k);
    for (i = 1 ; i <= k ; ++i){
        fscanf (fin,"%d%d",&x,&y);
        len = adauga(x , y);
        curr = 0;
        update(x , y , len , 1);

    }
    fscanf (fin,"%d",&q);
    for (i = 1 ; i <= q ; ++i){
        fscanf (fin,"%d",&tip);
        if (tip == 1){
            fscanf (fin,"%d%d",&x,&y);
            len = adauga(x , y);
            curr = 0;
            update (x , y , len , 1);
        }
        else if (tip == 2){
            fscanf (fin,"%d%d",&x,&y);
            len = adauga(x , y);
            curr = 0;
            update (x , y , len , -1);
        }
        else {
            fscanf (fin,"%d%d%d%d",&x,&y,&t1,&t2);
            fprintf (fout,"%lld\n",query (x , y , t1 , t2));
        }
    }
    return 0;
}

Compilation message (stderr)

traffickers.cpp: In function 'void dfs_lant(int, int)':
traffickers.cpp:23:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<v[nod].size();++i){
              ~^~~~~~~~~~~~~~
traffickers.cpp:43:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i=0;i<v[nod].size();++i){
                  ~^~~~~~~~~~~~~~
traffickers.cpp: In function 'int main()':
traffickers.cpp:180:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf (fin,"%d",&n);
     ~~~~~~~^~~~~~~~~~~~~
traffickers.cpp:182:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf (fin,"%d%d",&x,&y);
         ~~~~~~~^~~~~~~~~~~~~~~~~~
traffickers.cpp:204:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf (fin,"%d",&k);
     ~~~~~~~^~~~~~~~~~~~~
traffickers.cpp:206:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf (fin,"%d%d",&x,&y);
         ~~~~~~~^~~~~~~~~~~~~~~~~~
traffickers.cpp:212:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf (fin,"%d",&q);
     ~~~~~~~^~~~~~~~~~~~~
traffickers.cpp:214:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf (fin,"%d",&tip);
         ~~~~~~~^~~~~~~~~~~~~~~
traffickers.cpp:216:20: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             fscanf (fin,"%d%d",&x,&y);
             ~~~~~~~^~~~~~~~~~~~~~~~~~
traffickers.cpp:222:20: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             fscanf (fin,"%d%d",&x,&y);
             ~~~~~~~^~~~~~~~~~~~~~~~~~
traffickers.cpp:228:20: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             fscanf (fin,"%d%d%d%d",&x,&y,&t1,&t2);
             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 45 / 45
• Subtask 3: 40 / 40