Submission #481080

#	Time	Username	Problem	Language	Result	Execution time	Memory
481080		DJeniUp	Railway (BOI17_railway)	C++17	100 / 100	254 ms	51788 KiB

railway

#pragma GCC Optimize("O3")
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll>pairll;
typedef pair<ll,pairll>pairlll;
typedef pair<pairll,pairll>pairllll;
typedef long double ld;
typedef pair<ll,string>pairls;

#define INF 1000000000000007
#define MOD 1000000007
#define pb push_back
#define fr first
#define sc second
#define endl '\n'

ll n,m,k,f[100007],t[100007][37],a[100007],b[100007],F,res[100007];

vector<pairll>v[100007];
vector<ll>d[50007];

queue<ll>R;

void S(ll x,ll y){
    F++;
    a[x]=F;
    t[x][0]=y;
    for(int i=1;i<=26;i++){
        t[x][i]=t[t[x][i-1]][i-1];
    }
    for(int i=0;i<v[x].size();i++){
        if(v[x][i].fr!=y)S(v[x][i].fr,x);
    }
    F++;
    b[x]=F;
    return ;
}

ll up(ll x,ll y){
    if(a[x]<a[y] && b[y]<b[x])return x;
    if(a[y]<a[x] && b[x]<b[y])return y;

    for(int i=26;i>=0;i--){
        if((a[t[x][i]]<a[y] && b[y]<b[t[x][i]]) || t[x][i]==0)continue;
        x=t[x][i];
    }
    return t[x][0];
}

bool mcp(ll d1,ll d2){
    return a[d1]<a[d2];
}

ll D(ll x,ll y,ll z){
    res[z]+=f[x];
    for(int i=0;i<v[x].size();i++){
        if(v[x][i].fr!=y)res[z]+=D(v[x][i].fr,x,v[x][i].sc);
    }
    return res[z];
}

int main() {
    
    cin>>n>>m>>k;
    for(int i=1;i<n;i++){
        ll l,r;
        cin>>l>>r;
        v[l].pb({r,i});
        v[r].pb({l,i});
    }
    S(1,0);
    for(int i=1;i<=m;i++){
        ll s;
        cin>>s;
        while(s--){
            ll l;
            cin>>l;
            d[i].pb(l);
        }
        sort(d[i].begin(), d[i].end(),mcp);
        for(int j=0;j<d[i].size();j++){
            f[d[i][j]]++;
            f[up(d[i][j],d[i][(j+1)%d[i].size()])]--;
        }
    }
    D(1,0,0);
    for(int i=1;i<n;i++){
        if(res[i]>=k)R.push(i);
    }
    cout<<R.size()<<endl;
    while(R.size()>0){
        cout<<R.front()<<" ";
        R.pop();
    }
}

Compilation message (stderr)

railway.cpp:1: warning: ignoring '#pragma GCC Optimize' [-Wunknown-pragmas]
    1 | #pragma GCC Optimize("O3")
      | 
railway.cpp: In function 'void S(ll, ll)':
railway.cpp:35:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for(int i=0;i<v[x].size();i++){
      |                 ~^~~~~~~~~~~~
railway.cpp: In function 'll D(ll, ll, ll)':
railway.cpp:60:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |     for(int i=0;i<v[x].size();i++){
      |                 ~^~~~~~~~~~~~
railway.cpp: In function 'int main()':
railway.cpp:85:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |         for(int j=0;j<d[i].size();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