Submission #212113

#	Time	Username	Problem	Language	Result	Execution time	Memory
212113		Ruxandra985	Traffickers (RMI18_traffickers)	C++14	0 / 100	3584 ms	39416 KiB

traffickers

#include <bits/stdc++.h>
#define DIMN 100010
using namespace std;
int eul[2*DIMN] , first[DIMN] , nv[2*DIMN] , tt[DIMN] , nivel[DIMN] , logg[2*DIMN];
int rmq[20][2*DIMN];
vector <int> v[DIMN];
set <pair <int,int> > stare[DIMN];
int elem;
void dfs (int nod , int fth , int lvl){
    int i , vecin;

    eul[++elem] = nod;
    first[nod] = elem;
    nv[elem] = lvl;
    tt[nod] = fth;
    nivel[nod] = lvl;

    for (i=0;i<v[nod].size();i++){
        vecin = v[nod][i];
        if (vecin != fth){
            dfs(vecin , nod , lvl + 1);
            eul[++elem] = nod;
            nv[elem] = lvl;
        }
    }

}
int query (int x, int y){
    int px , py , len;

    px = first[x];
    py = first[y];

    if (px > py)
        swap(px , py);

    len = py - px + 1;
    len = logg[len]; /// cea mai mare p2 <= len

    if (nv[ rmq[len][px] ] < nv[ rmq[len][py - (1 << len) + 1] ])
        return eul[ rmq[len][px] ];
    else return eul[ rmq[len][py - (1 << len) + 1] ];

}
void adauga (int x , int y){
    int lca , nod , poz , len;
    lca = query(x , y); /// dc sa mai faci for cand poti face asta?
    len = nivel[x] + nivel[y] - 2 * nivel[lca] + 1;

    nod = x;
    poz = 0;
    while (nod != tt[lca]){
        stare[nod].insert(make_pair(poz , len));
        poz++;
        if (poz == len)
            poz = 0;
        nod = tt[nod];
    }

    nod = y;
    poz = len - 1;
    while (nod != lca){
        stare[nod].insert(make_pair(poz , len));
        poz--;
        if (poz == -1)
            poz = len - 1;
        nod = tt[nod];
    }
}
void sterge (int x , int y){
    int lca , nod , poz , len;
    lca = query(x , y); /// dc sa mai faci for cand poti face asta?
    len = nivel[x] + nivel[y] - 2 * nivel[lca] + 1;

    nod = x;
    poz = 0;
    while (nod != tt[lca]){
        stare[nod].erase(make_pair(poz , len));
        poz++;
        if (poz == len)
            poz = 0;
        nod = tt[nod];
    }

    nod = y;
    poz = len - 1;
    while (nod != lca){
        stare[nod].erase(make_pair(poz , len));
        poz--;
        if (poz == -1)
            poz = len - 1;
        nod = tt[nod];
    }
}
long long afla (int x , int y , int t1 , int t2){
    int lca , nod , len , rest;
    long long sol = 0;
    lca = query(x , y); /// dc sa mai faci for cand poti face asta?

    nod = x;
    while (nod != tt[lca]){

        for (set <pair <int,int> > :: iterator it = stare[nod].begin() ; it != stare[nod].end() ; it++){

            len = it->second;
            rest = it->first;
            if (rest)
                sol += (t2 / len) + (t2 % len >= rest) - ((t1 - 1) / len) + ((t1 - 1) % len >= rest);
            else {
                if (len != 1)
                    sol += (t2 / len) - ((t1 - 1) / len);
                else sol += (t2 - t1 + 1);
            }
        }

        nod = tt[nod];
    }

    nod = y;
    while (nod != lca){

        for (set <pair <int,int> > :: iterator it = stare[nod].begin() ; it != stare[nod].end() ; it++){

            len = it->second;
            rest = it->first;
            if (rest)
                sol += (t2 / len) + (t2 % len >= rest) - ((t1 - 1) / len) + ((t1 - 1) % len >= rest);
            else {
                if (len != 1)
                    sol += (t2 / len) - ((t1 - 1) / len);
                else sol += (t2 - t1 + 1);
            }

        }

        nod = tt[nod];
    }
    return sol;
}
int main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    int n , i , x , y , tip , k , q , powe , t1 , t2;
    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);
    }

    dfs(1 , 0 , 0);


    for (i = 2 ; i <= elem ; i++)
        logg[i] = 1 + logg[i / 2];

    for (i = 1 ; i <= elem ; i++)
        rmq[0][i] = i;

    for (powe = 1 ; (1 << powe) <= elem ; powe++){
        for (i = 1 ; i + (1 << powe) - 1 <= elem ; i++){

            if (nv[ rmq[powe-1][i] ] < nv[ rmq[powe-1][i + (1 << (powe - 1) )] ])
                rmq[powe][i] = rmq[powe-1][i];
            else rmq[powe][i] = rmq[powe-1][i + (1 << (powe - 1) )];

        }
    }

    fscanf (fin,"%d",&k);

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

    }

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

Compilation message (stderr)

traffickers.cpp: In function 'void dfs(int, int, int)':
traffickers.cpp:18:15: 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:145: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:147: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:171: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:174: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:179: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:181: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:183: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:187: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:191: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: 0 / 15
• Subtask 2: 0 / 45
• Subtask 3: 0 / 40