Submission #464210

#	Time	Username	Problem	Language	Result	Execution time	Memory
464210		idas	Railway (BOI17_railway)	C++11	100 / 100	269 ms	54540 KiB

railway

#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], b[N];
map<pii, int> pth, con;

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

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;
        FOR(j, 0, s)
        {
            int x; cin >> x;
            cnt[x-1]++;
            b[x-1].PB(i);
        }
    }

    ord(0, -1);

    FOR(i, 0, m)
    {
        sort(inf[i].begin(), inf[i].end());
        FOR(j, 0, inf[i].size())
        {
            int b=lca(inf[i][j].S, inf[i][(j+1)%(int)inf[i].size()].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 'int main()':
railway.cpp:2:51: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    2 | #define FOR(i, begin, end) for(int i = (begin); i < (end); i++)
      |                                                   ^
railway.cpp:134:9: note: in expansion of macro 'FOR'
  134 |         FOR(j, 0, inf[i].size())
      |         ^~~
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);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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