Submission #178849

#	Time	Username	Problem	Language	Result	Execution time	Memory
178849		Ruxandra985	Railway (BOI17_railway)	C++14	29 / 100	384 ms	55880 KiB

railway

#include <bits/stdc++.h>
#define DIMN 100010
using namespace std;
int ok[DIMN],lvl[DIMN] , f[DIMN] , d[DIMN] , l[DIMN] , up[DIMN] , fth[20][DIMN];
int lg[DIMN] , poz[DIMN];
int lnt = 0;
map <pair <int,int> , int> mc , nr_mch;
pair <int,int> muchie[DIMN];
stack <int > st;
vector <int> v[DIMN] , w[DIMN] , dfs_tree[DIMN] , tr[DIMN] ;
vector <pair <int,int> > aint[DIMN];
int x;
void precalc (int nod){
    int i,vecin;
    d[nod]=1;
    f[nod]=1;
    for (i=0;i<v[nod].size();i++){
        vecin=v[nod][i];
        if (!f[vecin]){
            lvl[vecin]=1+lvl[nod];
            dfs_tree[nod].push_back(vecin);
            precalc (vecin);
            d[nod]+=d[vecin];

        }
    }
}

void dfs_lant(int nod,int tata){
    int i,vecin,ok=0,maxi,fiu;
    fth[0][nod] = tata;
    f[nod] = 1;
    maxi=0;
    fiu=0;
    for (i=0;i<dfs_tree[nod].size();i++){
        vecin=dfs_tree[nod][i];
        if (vecin != tata){
            ok=1;
            dfs_lant(vecin,nod);
            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<dfs_tree[nod].size();i++){
            vecin=dfs_tree[nod][i];
            if (vecin!=tata && vecin!=fiu)
                up[l[vecin]]=nod; /// din lantul vecinului trecem in lantul nodului
        }
    }
}

pair <int,int> lca (int n , int x , int y){
    int dif , p2 , swapped = 0;
    //if (x == 1 && y == 5)
      //  printf ("a");
    /// aducem pe ac nivel
    if (lvl[x] < lvl[y]){
        swapped = 1;
        swap(x , y); /// x e mai jos
    }
    dif = lvl[x] - lvl[y] - 1;
    /// stramosul dif al lui x

     while (dif > 0 && x!=0){
        x=fth[lg[dif]][x];
        dif=dif-(1<<lg[dif]);
    }
    /// acum sunt pe acelasi nivel
    if (fth[0][x] == y){ /// y era tatal lui x
        if (!swapped)
            return make_pair(x , -1);
        else return make_pair(-1 , x);
    }
    if (dif != -1)
        x = fth[0][x];

    for (p2 = lg[n] ; p2>=0 ; p2--){
        if (fth[p2][x] != fth[p2][y]){
            x = fth[p2][x];
            y = fth[p2][y];
        }
    }
    if (!swapped)
        return make_pair(x , y);
    else return make_pair(y , x);
}
inline void lazy_update (int lant , int nod,int st,int dr){
    if (!tr[lant][nod]) /// nu ii trb lazy
        return;
    if (st<dr){ /// nu e frunza
        tr[lant][2*nod]+=tr[lant][nod]; /// pass lazy
        tr[lant][2*nod+1]+=tr[lant][nod];
    }
    aint[lant][nod].first+=tr[lant][nod];
    tr[lant][nod]=0;
}
void update_aint (int lant , int nod , int st , int dr , int l , int r , int val , int lts){
    int mid = (st + dr)/2;
    lazy_update (lant , nod,st,dr);
    if (aint[lant][nod].second == lts) /// latest influenteaza aici
        return;
    if (l <= st && dr <= r){
        tr[lant][nod] += val; /// la tot intervalul se adauga val
        aint[lant][nod].second = lts;
        lazy_update (lant , nod,st,dr);
        return;
    }

    if (l <= mid)
        update_aint (lant , 2*nod , st , mid , l , r, val , lts);

    if (mid+1 <= r)
        update_aint (lant , 2*nod+1 , mid+1 , dr , l , r, val , lts);

    lazy_update (lant , 2*nod,st,mid);
    lazy_update (lant , 2*nod+1,mid+1,dr);


}

void update (int x , int y , int val , int lts){
    if (l[x]!=l[y]){ /// avansam
        if (lvl[up[l[x]]]>lvl[up[l[y]]]){
            update(up[l[x]] , y , val , lts);
            update_aint( l[x] , 1 , 0 , w[l[x]].size()-1 , 0 , poz[x] , val , lts);
        }
        else {
            update (x,up[l[y]] , val , lts);
            update_aint(l[y],1,0,w[l[y]].size()-1,0,poz[y] , val , lts);
        }
    }
    else {
        return update_aint(l[x],1,0,w[l[x]].size()-1,min(poz[y] , poz[x]),max(poz[y] , poz[x]) , val , lts);
    }

}

int query_aint (int lant,int nod,int st,int dr,int px){
    int mid;
    lazy_update(lant , nod , st , dr);
    if (st == dr)
        return aint[lant][nod].first;
    mid=(st+dr)/2;
    if (px<=mid)
        return query_aint(lant,2*nod,st,mid,px);
    else
        return query_aint(lant,2*nod+1,mid+1,dr,px);
}

int main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    int n, m , i , x , y , p , vecin, sol , nr , j , a , b , frc;
    pair <int,int> z;
    fscanf (fin,"%d%d%d",&n,&m,&frc);
    for (i=1;i<n;i++){
        fscanf (fin,"%d%d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
        nr_mch[make_pair(x , y)] = i;
        nr_mch[make_pair(y , x)] = i;
        muchie[i] = make_pair(x , y);
    }

    for (i=1;i<=n;i++){
        if (!f[i])
            precalc(i);
    }

    memset (f , 0 , sizeof ( f ));

    for (i=1;i<=n;i++){
        if (!f[i])
            dfs_lant(i , 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++;
        }
    }
    /// folosesti aint

    for (i=1;i<=lnt;i++){
        aint[i].resize(w[i].size()*5);
        tr[i].resize(w[i].size()*5);
    }

    /// ai precalculat pentru heavy

    for (i=2;i<=n;i++){
        lg[i]=lg[i/2]+1;
    }
    int k = 1;
    while ((1<<k)<=n){
        for (i=1;i<=n;i++){
            fth[k][i] = fth[k-1][fth[k-1][i]] ;
        }
        k++;
    }

    /// ai precalculat pe lca in log pt ca ti a fost lene sa faci cu query in o(1)

    for (i=1;i<=m;i++){
        fscanf (fin,"%d",&nr);
        for (j=1;j<=nr;j++){
            fscanf (fin,"%d",&b);
            if (j == 1){
                a = b;
            }
            else {
                z = lca (n , a , b);
                if (z.first != -1)
                    update (a , z.first , 1 , i ); /// si cu latest
                if (z.second != -1)
                    update (b , z.second , 1 , i); /// si cu latest
                if (z.first != -1)
                    a = fth[0][z.first];
            }
        }
    }
    sol = 0;
    for (i=1;i<=n;i++){
        if (query_aint(l[i] , 1 , 0 , w[l[i]].size() - 1 , poz[i]) >= frc){
            ok[++sol] = nr_mch[make_pair(i , fth[0][i])];
        }
    }
    sort (ok + 1 , ok + sol + 1);
    fprintf (fout,"%d\n",sol);
    for (i=1;i<=sol;i++)
        fprintf (fout,"%d ",ok[i]);
    return 0;
}

Compilation message (stderr)

railway.cpp: In function 'void precalc(int)':
railway.cpp:17:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<v[nod].size();i++){
              ~^~~~~~~~~~~~~~
railway.cpp: In function 'void dfs_lant(int, int)':
railway.cpp:35:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<dfs_tree[nod].size();i++){
              ~^~~~~~~~~~~~~~~~~~~~~
railway.cpp:53:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i=0;i<dfs_tree[nod].size();i++){
                  ~^~~~~~~~~~~~~~~~~~~~~
railway.cpp: In function 'int main()':
railway.cpp:165:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf (fin,"%d%d%d",&n,&m,&frc);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
railway.cpp:167: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);
         ~~~~~~~^~~~~~~~~~~~~~~~~~
railway.cpp:221:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf (fin,"%d",&nr);
         ~~~~~~~^~~~~~~~~~~~~~
railway.cpp:223:20: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             fscanf (fin,"%d",&b);
             ~~~~~~~^~~~~~~~~~~~~

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