Submission #1093093

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093093		MrPavlito	Railway (BOI17_railway)	C++17	100 / 100	80 ms	34248 KiB

railway

#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define sc second
///#define endl "\n"
#define pii pair<int,int>

using namespace std;

const int MAXN = 1e5+5;
const int mod7 = 1e9+7;
const long long inf = 1e18;
const int lg = 18;

int up[MAXN][lg];
int dist[MAXN];
int tin[MAXN];
int tout[MAXN];
int cnt[MAXN];
int t = 1;
int n,m,k;
vector<vector<int>> graf(MAXN);


void dfs(int nod, int p, int d)
{
    dist[nod] = d;
    up[nod][0] = p;
    tin[nod] = t++;
    for(auto x: graf[nod])if(x!=p)dfs(x,nod,d+1);
    tout[nod] = t++;
}

void fillUp()
{
    for(int i=1; i<lg; i++)
    {
        for(int j=1; j<=n; j++)
        {
            up[j][i] = up[up[j][i-1]][i-1];
        }
    }
}

int lca(int u,int v)
{
    if(u == v)return u;
    if(tin[u] < tin[v] && tout[u] > tout[v])return u;
    if(tin[u] > tin[v] && tout[u] < tout[v])return v;

    for(int i=lg-1; i>=0; i--)
    {
        int probaj = up[v][i];
        if(!(tin[probaj] < tin[u] && tout[probaj] > tout[u]))v = probaj;
    }
    return up[v][0];
}

void dfs2(int nod, int p)
{
    for(auto x:graf[nod])
    {
        if(x==p)continue;
        dfs2(x,nod);
        cnt[nod] += cnt[x];
    }
}

signed main()
{
    ios_base::sync_with_stdio(false),cin.tie(0), cout.tie(0);
    int tt=1;
    //cin >> tt;
    while(tt--)
    {

        cin >> n >> m>> k;
        vector<pii>svi_putevi(n-1);
        for(int i=0; i<n-1; i++)
        {
            int a,b;cin >> a >> b;
            svi_putevi[i].fi = a;
            svi_putevi[i].sc = b;
            graf[a].pb(b);
            graf[b].pb(a);
        }
        dfs(1,1,0);
        fillUp();
        for(int i=0; i<m; i++)
        {
            int x;cin >> x;
            vector<pii> v(x);
            for(int j=0; j<x; j++)
            {
                cin >> v[j].sc;
                v[j].fi = tin[v[j].sc];
            }
            sort(all(v));
            reverse(all(v));
            //for(auto x: v)cout << x.sc << " "; cout << endl;
           for(int j=0; j<x; j++)
           {
                int cale = lca(v[j].sc, v[(j+1)%x].sc);
                cnt[cale]-=2;
                cnt[v[j].sc] ++;
                cnt[v[(j+1)%x].sc] ++;
           }
        }
        dfs2(1,1);
        for(int i=1; i<=n; i++)cnt[i]/=2;
        vector<int> rez;
        for(int i=0; i<n-1; i++)
        {
            int a = svi_putevi[i].fi;
            int b = svi_putevi[i].sc;
            if(dist[a] > dist[b])swap(a,b);
            if(cnt[b] >= k)rez.pb(i+1);
        }
        cout << rez.size() << endl;
        for(auto x: rez)cout << x << " ";

    }
}

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