Submission #212187

# Submission time Handle Problem Language Result Execution time Memory
212187 2020-03-22T12:44:18 Z Ruxandra985 Traffickers (RMI18_traffickers) C++14
15 / 100
3500 ms 524292 KB
#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] , idx_aint[DIMN];
vector < map <int,int> > aint[DIMN];
vector <int> v[DIMN] , w[DIMN];
multiset <pair <int,pair <int,int> > > stare[DIMN];
int elem , lnt;
void dfs (int nod , int fth , int nivel){
    int i , vecin;

    tt[nod] = fth;
    lvl[nod] = nivel;
    d[nod] = 1;

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

}
void dfs_lant(int nod){
    int i,vecin,ok=0,maxi,fiu;
    maxi=0;
    fiu=0;
    for (i=0;i<v[nod].size();i++){
        vecin=v[nod][i];
        if (vecin!=tt[nod]){
            ok=1;
            dfs_lant(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!=tt[nod] && vecin!=fiu)
                up[l[vecin]]=nod; /// din lantul vecinului trecem in lantul nodului
        }
    }
}
void build_aint (int lant , int p , int st , int dr){
    int mid = (st + dr)/2;

    if (st == dr){
        idx_aint[w[lant][st]] = p;
        return;
    }

    build_aint(lant , 2 * p , st , mid);
    build_aint(lant , 2 * p + 1 , mid + 1 , dr);


}
void update_aint (int lant , int p , int st , int dr , int l , int r){
    int mid , len , rest;
    if (st == dr){
        return;
    }
    mid=(st+dr)/2;
    if (l <= mid)
        update_aint(lant , 2 * p , st , mid , l , r);
    if (mid + 1 <= r)
        update_aint(lant , 2 * p + 1 , mid + 1 , dr , l , r);
    for (len = 1 ; len <= 20 ; len++){
        for (rest = 0 ; rest < len ; rest++)
            aint[lant][p][len * 100 + rest] = aint[lant][2 * p][len * 100 + rest] + aint[lant][2 * p + 1][len * 100 + rest];
    }
}
void update (int x , int y){
    if (l[x]!=l[y]){ /// avansam
        if (lvl[up[l[x]]]>lvl[up[l[y]]]){
            update ( up[l[x]] , y );

            update_aint (l[x] , 1 , 0 , w[l[x]].size()-1 , 0 , poz[x] );
        }
        else{
            update ( x , up[l[y]] );

            update_aint( l[y] , 1 , 0 , w[l[y]].size()-1 , 0 , poz[y] );
        }
    }
    else {
        update_aint( l[x] , 1 , 0 , w[l[x]].size()-1 , min(poz[x],poz[y]) , max(poz[x],poz[y]) );
    }
}
long long query_aint (int lant , int p , int st , int dr , int px , int py , int t1 , int t2){
    int sol=0 , mid , len , rest;
    if (px <= st && dr <= py){

        for (len = 1 ; len <= 20 ; len ++){
            for (rest = 0 ; rest < len ; rest++){
                //if (aint[lant][p][len * 100 + rest])
                  //  printf ("%d %d %d\n" , len , rest ,aint[lant][p][len * 100 + rest] );
                sol += aint[lant][p][len * 100 + rest] * ( (t2 / len) + (t2 % len >= rest) - ((t1 - 1) / len) - ((t1 - 1) % len >= rest));
            }
        }

        return sol;
    }
    mid = (st + dr)/2;
    if (px <= mid)
        sol = sol + query_aint(lant , 2 * p , st , mid , px , py , t1 , t2);
    if (mid+1 <= py)
        sol = sol + query_aint(lant , 2 * p + 1 , 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(l[x] , 1 , 0 , w[l[x]].size()-1 , 0 , poz[x] , t1 , t2);
        else{
            return query(x , up[l[y]] , t1 , t2) + query_aint(l[y] , 1 , 0 , w[l[y]].size()-1 , 0 , poz[y] , t1 , t2);
        }
    }
    else{
        return query_aint(l[x] , 1 , 0 , w[l[x]].size()-1 , min(poz[x],poz[y]) , max(poz[x],poz[y]) , t1 , t2);
    }
}
void adauga (int x , int y , int val , int op){
    int lca , nod , poz , len , i;
    nod = x;
    for (i = 0 ; i < 20 ; i++){
        f[nod] = op;
        nod = tt[nod];
    }

    nod = y;
    for (i = 0 ; i < 20 ; i++){
        if (f[nod] == op){
            lca = nod;
            break;
        }
        f[nod] = op;
        nod = tt[nod];
    }
    len = lvl[x] + lvl[y] - 2 * lvl[lca] + 1;

    nod = x;
    poz = 0;
    while (nod != tt[lca]){
        aint[l[nod]][idx_aint[nod]][len * 100 + poz] += val;
        poz++;
        nod = tt[nod];
    }

    nod = y;
    poz = len - 1;
    while (nod != lca){
        aint[l[nod]][idx_aint[nod]][len * 100 + poz] += val;
        poz--;
        nod = tt[nod];
    }
}
int main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    int n , i , x , y , tip , k , q , t1 , t2 , p , vecin;
    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 , 1);
    dfs_lant(1);

    /// 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].resize(w[i].size()*5);
        build_aint(i , 1 , 0 , w[i].size() - 1);
    }


    fscanf (fin,"%d",&k);
    int op = 1;
    for (i = 1 ; i <= k ; i++){
        fscanf (fin,"%d%d",&x,&y);
        adauga(x , y , 1 , ++op);
        update(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 , 1 , ++op);
            update (x , y);
        }
        else if (tip == 2){
            fscanf (fin,"%d%d",&x,&y);
            adauga(x , y , -1 , ++op);
            update (x , y);
        }
        else {
            fscanf (fin,"%d%d%d%d",&x,&y,&t1,&t2);
            fprintf (fout,"%lld\n",query (x , y , t1 , t2));
        }
    }
    return 0;
}

Compilation message

traffickers.cpp: In function 'void dfs(int, int, int)':
traffickers.cpp:17:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<v[nod].size();i++){
              ~^~~~~~~~~~~~~~
traffickers.cpp: In function 'void dfs_lant(int)':
traffickers.cpp:30:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<v[nod].size();i++){
              ~^~~~~~~~~~~~~~
traffickers.cpp:48: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:173: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:175: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:198: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:201: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:206: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:208: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:210: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:215: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:220: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);
             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
traffickers.cpp: In function 'void adauga(int, int, int, int)':
traffickers.cpp:134:9: warning: 'lca' may be used uninitialized in this function [-Wmaybe-uninitialized]
     int lca , nod , poz , len , i;
         ^~~
# Verdict Execution time Memory Grader output
1 Correct 25 ms 13056 KB Output is correct
2 Correct 241 ms 32120 KB Output is correct
3 Correct 194 ms 26364 KB Output is correct
# Verdict Execution time Memory Grader output
1 Incorrect 2674 ms 176208 KB Output isn't correct
2 Incorrect 2299 ms 139984 KB Output isn't correct
3 Incorrect 2772 ms 196680 KB Output isn't correct
4 Incorrect 2590 ms 168304 KB Output isn't correct
5 Incorrect 2445 ms 155396 KB Output isn't correct
6 Incorrect 2527 ms 161132 KB Output isn't correct
7 Incorrect 2550 ms 166248 KB Output isn't correct
8 Incorrect 2828 ms 206284 KB Output isn't correct
9 Incorrect 2879 ms 213272 KB Output isn't correct
# Verdict Execution time Memory Grader output
1 Execution timed out 3562 ms 425480 KB Time limit exceeded
2 Execution timed out 3610 ms 516460 KB Time limit exceeded
3 Runtime error 2617 ms 524288 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Execution timed out 3586 ms 336196 KB Time limit exceeded
5 Execution timed out 3591 ms 312708 KB Time limit exceeded
6 Runtime error 2852 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 2385 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 2353 ms 524288 KB Execution killed with signal 9 (could be triggered by violating memory limits)