Submission #1308109

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308109		harryleee	Railway (BOI17_railway)	C++20	100 / 100	111 ms	39776 KiB

railway

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
#define mp make_pair
const int N=1e5+50,lg=18;
vector<int>E[N];
int n,q,K;
int in[N],tajm,out[N],par[N][lg+1],depth[N];
void DFS1(int u,int p=0){
    in[u]=++tajm;
    par[u][0]=p;depth[u]=depth[p]+1;
    for(int i=1;i<=lg;i++)par[u][i]=par[par[u][i-1]][i-1];
    for(auto i:E[u])if(i!=p)DFS1(i,u);
    out[u]=tajm;
}
int LCA(int u,int v){
    if(depth[u]<depth[v])swap(u,v);
    for(int i=lg;i>=0;i--)if(depth[par[u][i]]>=depth[v])u=par[u][i];if(u==v)return u;
    for(int i=lg;i>=0;i--)if(par[u][i]!=par[v][i])u=par[u][i],v=par[v][i];return par[u][0];
}
int val[N],dp[N];
vector<int>res;
map<pair<int,int>,int>mapa;
void DFS(int u,int p=0){
    dp[u]=val[u];
    for(auto i:E[u])if(i!=p)DFS(i,u),dp[u]+=dp[i];
    if(p!=0&&dp[u]>=2*K)res.pb(mapa[mp(u,p)]);
}
int main(){
    scanf("%i%i%i",&n,&q,&K);
    for(int i=1;i<n;i++){
        int u,v;scanf("%i%i",&u,&v);
        E[u].pb(v),E[v].pb(u);
        mapa[{u,v}]=mapa[{v,u}]=i;
    }
    DFS1(1);
    while(q--){
        int m;scanf("%i",&m);
        int a[m];for(int i=0;i<m;i++)scanf("%i",&a[i]);
        sort(a,a+m,[&](int i,int j){return in[i]<in[j];});
        for(int i=0;i<m;i++){
            int u=a[i],v=a[0];
            if(i<m-1)v=a[i+1];
            int c=LCA(u,v);
            val[u]++,val[v]++;
            val[c]-=2;
        }
    }
    DFS(1);
    sort(res.begin(),res.end());
    printf("%i\n",res.size());
    for(auto i:res)printf("%i ",i);printf("\n");
    return 0;
}

Compilation message (stderr)

railway.cpp: In function 'int main()':
railway.cpp:55:14: warning: format '%i' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wformat=]
   55 |     printf("%i\n",res.size());
      |             ~^    ~~~~~~~~~~
      |              |            |
      |              int          std::vector<int>::size_type {aka long unsigned int}
      |             %li
railway.cpp:34:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |     scanf("%i%i%i",&n,&q,&K);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
railway.cpp:36:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |         int u,v;scanf("%i%i",&u,&v);
      |                 ~~~~~^~~~~~~~~~~~~~
railway.cpp:42:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |         int m;scanf("%i",&m);
      |               ~~~~~^~~~~~~~~
railway.cpp:43:43: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |         int a[m];for(int i=0;i<m;i++)scanf("%i",&a[i]);
      |                                      ~~~~~^~~~~~~~~~~~

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