Submission #179650

#	Time	Username	Problem	Language	Result	Execution time	Memory
179650		Ruxandra985	Railway (BOI17_railway)	C++14	100 / 100	297 ms	46280 KiB

railway

#include <bits/stdc++.h>
#define DIMN 100010
using namespace std;
int eul[5*DIMN],nv[5*DIMN],first[DIMN];
int d[20][5*DIMN] , el , elem, st[DIMN] , ed[DIMN] , sp[DIMN] , idk[DIMN] , ok[DIMN];
int lg[5*DIMN] , fth[DIMN];
vector <int> v[DIMN];
map <pair <int,int> , int> nr_mch;
void dfs (int nod , int tt ,int niv){
    int i,vecin;
    fth[nod] = tt;
    eul[++elem]=nod;
    nv[elem] = niv;
    first[nod] = elem; /// prima poz;
    for (i=0;i<v[nod].size();i++){
        vecin=v[nod][i];
        if (vecin != tt){
            dfs(vecin , nod ,niv+1);
            eul[++elem]=nod;
            nv[elem]=niv;
        }
    }
    ed[nod] = elem; /// pana la elem e intervalul
}

int query (int x,int y){
    int px,py,len;
    px=first[x];
    py=first[y];
    /// minimul din intervalul px py
    /// in d e pozitia din eul unde e nivelul minim
    if (px>py)
        swap(px,py);
    len = py-px+1;
    if (nv[ d[lg[len]][px] ] < nv[ d[lg[len]][py-(1<<lg[len])+1] ])
        return d[lg[len]][px];
    return d[lg[len]][py-(1<<lg[len])+1];
}
int cmp (int x , int y){

    return first[x] < first[y];


}
void dfs_sp (int nod,int tt){

    int i,vecin;
    for (i=0;i<v[nod].size();i++){
        vecin=v[nod][i];
        if (vecin != tt){
            dfs_sp(vecin , nod);
            sp[nod]+=sp[vecin];
        }
    }

}
int main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    int n , m , i , x , y , sol , nr , j , frc , powe , nod;
    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;
    }

    dfs(1 , 0 , 0);


    for (i=2;i<=elem;i++){
        lg[i]=lg[i/2]+1;
    }
    for (i=1;i<=elem;i++){
        d[0][i] = i;
    }

    for (powe=1;powe<=lg[elem];powe++){
        for (i=1;i + (1<<powe)-1 <=elem;i++){
            if (nv[d[powe-1][i]] < nv[d[powe-1][i + (1<<(powe-1))]])
                d[powe][i] = d[powe-1][i];
            else d[powe][i] = d[powe-1][i + (1<<(powe-1))];
        }
    }

    /// 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);
        nod = 0;
        for (j=1;j<=nr;j++){
            fscanf (fin,"%d",&idk[j]);
            if (j == 1)
                nod = idk[j];
            else nod = eul[query (idk[j] , nod)];
        }
        idk[++nr] = nod; /// sa zicem ca adaugi si lca ul total
        sort (idk + 1 , idk + nr + 1 , cmp);
        int nra = nr;
        for (j=2;j<nra;j++){
            idk[++nr] = eul[query(idk[j] , idk[j+1])];
        }
        sort (idk + 1 , idk + nr + 1 , cmp);
        el = 0;
        for (j=1;j<=nr;j++){
            while (el && ed[st[el]] < first[idk[j]])
                el--;
            if (el){
                sp[idk[j]]++;
                sp[st[el]]--;
            }
            st[++el] = idk[j];
        }

    }
    dfs_sp(1 , 0);
    sol = 0;
    for (i=1;i<=n;i++){
        if (sp[i] >= frc){
            ok[++sol] = nr_mch[make_pair(i , fth[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 dfs(int, int, int)':
railway.cpp:15: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_sp(int, int)':
railway.cpp:48:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<v[nod].size();i++){
              ~^~~~~~~~~~~~~~
railway.cpp: In function 'int main()':
railway.cpp:63: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:65: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:93: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:96:20: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             fscanf (fin,"%d",&idk[j]);
             ~~~~~~~^~~~~~~~~~~~~~~~~~

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