Submission #172826

#	Time	Username	Problem	Language	Result	Execution time	Memory
172826		rzbt	Railway (BOI17_railway)	C++14	0 / 100	156 ms	24376 KiB

railway

#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define MAXN 100005
typedef long long ll;


using namespace std;

vector<pair<int,int> > niz[MAXN];
int predak[MAXN][20],ulaz[MAXN],izlaz[MAXN],dub[MAXN],zbir[MAXN];
int vreme;
vector<int> tg,res;

int n,m,k;

void dfs(int t,int o,int h){
    vreme++;
    ulaz[t]=vreme;
    dub[t]=h;
    predak[t][0]=o;
    for(auto x:niz[t])
        if(x.F!=o)dfs(x.F,t,h+1);
    izlaz[t]=vreme;


}
int lca(int a,int b){

    if(dub[a]<dub[b])swap(a,b);
    //printf("   %d %d\n",a,b);
    for(int i=19;i>=0;i--){
        if(predak[a][i]==0)continue;
        if(dub[predak[a][i]]>=dub[b])a=predak[a][i];
    }
    //printf("   %d %d\n",a,b);
    if(a==b)return a;
    for(int i=19;i>=0;i--){
        if(predak[a][i]!=predak[b][i]){
            a=predak[a][i];
            b=predak[b][i];
        }
    }

    return predak[a][0];
}

bool cmp(int a,int b){
    return ulaz[a]<ulaz[b];
}

void dfs2(int t,int o){

    for(auto x:niz[t]){
        if(x.F==o)continue;
        dfs2(x.F,t);
        if(zbir[x.F]>=k)res.pb(x.S);
        zbir[t]+=zbir[x.F];
    }
    //printf("   %d %d\n",t, zbir[t]);
    return;
}

int main()
{
    scanf("%d %d %d", &n, &m, &k);
    for(int i=1;i<n;i++){
        int t1,t2;
        scanf("%d %d", &t1, &t2);
        niz[t1].pb(mp(t2,i));
        niz[t2].pb(mp(t1,i));
    }
    dfs(1,0,0);
    for(int j=1;j<20;j++){
        for(int i=1;i<=n;i++){
            predak[i][j]=predak[predak[i][j-1]][j-1];
        }
    }
    for(int i=1;i<=m;i++){
        int bt;
        scanf("%d", &bt);
        tg.clear();
        for(int j=0;j<bt;j++){
            int t;
            scanf("%d", &t);
            tg.pb(t);
        }
        sort(all(tg),cmp);
        tg.pb(tg[0]);
        for(int j=0;j<bt;j++){
            //printf("   %d %d    %d\n",tg[j],tg[j+1],lca(tg[j],tg[j+1]));
            zbir[tg[j]]++;
            zbir[lca(tg[j],tg[j+1])]--;
        }
        //for(int i=1;i<=n;i++)printf("%d ",zbir[i]);
        //printf("\n");
    }
    dfs2(1,0);

    printf("%d\n",res.size());
    for(auto x:res)printf("%d ",x);

    return 0;
}

Compilation message (stderr)

railway.cpp: In function 'int main()':
railway.cpp:103:29: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
     printf("%d\n",res.size());
                   ~~~~~~~~~~^
railway.cpp:69:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &n, &m, &k);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
railway.cpp:72:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &t1, &t2);
         ~~~~~^~~~~~~~~~~~~~~~~~~
railway.cpp:84:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &bt);
         ~~~~~^~~~~~~~~~~
railway.cpp:88:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &t);
             ~~~~~^~~~~~~~~~

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