Submission #464122

#TimeUsernameProblemLanguageResultExecution timeMemory
464122idasRailway (BOI17_railway)C++11
23 / 100
1087 ms36588 KiB
#include <bits/stdc++.h>
#define FOR(i, begin, end) for(int i = (begin); i < (end); i++)
#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(nullptr)
#define F first
#define S second
#define PB push_back
#define MP make_pair

using namespace std;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef long long ll;

const int INF=1e9;

void setIO()
{
    FAST_IO;
}

void setIO(string s)
{
    FAST_IO;
    freopen((s+".in").c_str(), "r", stdin);
    freopen((s+".out").c_str(), "w", stdout);
}

const int N=1e5+10, M=5e4+10, L=27;

int n, m, k, cnt[N], par[N][L], dp[N];
vi ad[N];
map<pii, int> pth, con;

int id;
vi row[M];
unordered_set<int> in[M];
set<pii> inf[M];
void ord(int u, int pst, int idx)
{
    if(in[idx].count(u)) inf[idx].insert({id, u});
    id++;
    for(auto it : ad[u]){
        if(it==pst) continue;
        ord(it, u, idx);
    }
}

void pre(int u, int pst)
{
    for(auto it : ad[u]){
        if(it==pst) continue;
        par[it][0]=u;
        dp[it]=dp[u]+1;
        pre(it, u);
    }
}

int lift(int p, int x)
{
    FOR(i, 0, L) if(x&(1<<i))
    {
        p=par[p][i];
    }
    return p;
}

int lca(int a, int b)
{
    if(dp[a]>dp[b]) swap(a, b);
    int dif=dp[b]-dp[a];
    b=lift(b, dif);
    if(a==b) return a;
    for(int i=L-1; i>=0; i--){
        if(par[a][i]!=par[b][i]){
            a=par[a][i];
            b=par[b][i];
        }
    }
    return par[a][0];
}

int sms(int u, int pst)
{
    int tot=0;
    for(auto it : ad[u]){
        if(it==pst) continue;
        int k=sms(it, u);
        pth[{min(u, it), max(u, it)}]+=k;
        tot+=k;
    }
    return tot+cnt[u];
}

int main()
{
    setIO();
    cin >> n >> m >> k;
    FOR(i, 0, n-1)
    {
        int a, b;
        cin >> a >> b;
        ad[a-1].PB(b-1);
        ad[b-1].PB(a-1);
        con[{min(a-1, b-1), max(a-1, b-1)}]=i+1;
    }

    pre(0, -1);
    FOR(i, 1, L)
    {
        FOR(j, 0, n)
        {
            par[j][i]=par[par[j][i-1]][i-1];
        }
    }

    FOR(i, 0, m)
    {
        int s;
        cin >> s;
        //in.clear();
        //row.clear();
        //inf.clear();
        id=0;
        FOR(j, 0, s)
        {
            int x;
            cin >> x;
            in[i].insert(x-1);
            cnt[x-1]++;
        }
        ord(0, -1, i);
        /*
        FOR(i, 0, (int)inf.size())
        {
            int b=lca(inf[i].S, inf[(i+1)%(int)inf.size()].S);
            cnt[b]--;
        }
        */
        pii lst={-1, -1}, nd;
        for(auto it : inf[i]){
            if(lst.F==-1){
                lst=it;
                nd=it;
                continue;
            }
            int b=lca(lst.S, it.S);
            cnt[b]--;
            lst=it;
            nd=it;
        }
        pii st=*inf[i].begin();
        int b=lca(st.S, nd.S);
        cnt[b]--;
    }
    sms(0, -1);

    vi ans;
    for(auto it : pth){
        if(it.S>=k){
            ans.PB(con[{min(it.F.F, it.F.S), max(it.F.F, it.F.S)}]);
        }
    }

    cout << ans.size() << '\n';
    for(auto x : ans){
        cout << x << " ";
    }
}

Compilation message (stderr)

railway.cpp: In function 'void setIO(std::string)':
railway.cpp:24:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |     freopen((s+".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
railway.cpp:25:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |     freopen((s+".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...