Submission #484272

#	Time	Username	Problem	Language	Result	Execution time	Memory
484272		MohamedAliSaidane	Railway (BOI17_railway)	C++14	7 / 100	1095 ms	20284 KiB

railway

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef tuple<int,int,int> ti;
typedef unsigned long long ull;
typedef long double ld;
typedef vector<ll> vll;
typedef pair<ld,ld> pld;
#define pb push_back
#define popb pop_back()
#define pf push_front
#define popf pop_front
#define ff first
#define ss second
#define MOD (ll)(1000000007)
#define INF (ll) (1e18)
#define all(v) (v).begin(),(v).end()
const int nx[8] = {0, 0, 1, -1,1,1,-1,-1}, ny[8] = {1, -1, 0, 0,1,-1,1,-1}; //East, West, South, North+
ll gcd(ll a , ll b) {return b ? gcd(b , a % b) : a ;}
ll lcm(ll a, ll b){return (a / gcd(a, b)) * b;}
////////////******SOLUTION******\\\\\\\\\\\

const int MAX_N = 1e5 + 4;
int n, m, k;
vector<pii> edges;
vi adj[MAX_N];
int depth[MAX_N];
vi edsort;
map<pii,int> key;
bool comp(int a, int b)
{
    return depth[a] < depth[b];
}
set<int> co;
set<int> ans;
set<pii> ens;
int dfs(int node, int par)
{
    int rep= co.count(node) == 0? 0: 1;
    for(auto e: adj[node])
    {
        if(e == par)
            continue;
        if(dfs(e,node))
        {
            rep = 1;
            ans.insert(key[{min(e,node),max(e,node)}]);
        }
    }
    return rep;
}
void task4()
{
    for(int i = 1; i<=m; i ++)
    {
        int s; cin >> s;
        for(int u = 1; u <= s; u ++)
        {
            int x; cin >> x;
            co.insert(x);
        }
        dfs(*(co.begin()),-1);
        co.clear();
    }
    cout << ans.size() << '\n';
    for(auto e: ans)
     cout << e << ' ';
}
void solve()
{

    cin >> n >> m >> k;
    int maxt = 0;
    memset(depth,-1,sizeof(depth));
    for(int i = 1;  i<n;  i++)
    {
        int a, b;
        cin >> a >> b;
        key[{min(a,b),max(a,b)}] = i;
        adj[a].pb(b);
        adj[b].pb(a);
        maxt = max(maxt, max((int)adj[a].size(),(int)adj[b].size()));
    }
    if(maxt > 2)
    {
        task4();
        return ;
    }
    int root = 1;
    for(int i= 1; i <=n; i ++)
    {
        if(adj[i].size() == 1)
        {
            root = i;
            break;
        }
    }
    queue<pii> q;
    q.push({root,0});
    while(!q.empty())
    {
        int node = q.front().ff;
        int d= q.front().ss;
        q.pop();
        depth[node]= d;
        for(auto e: adj[node])
        {
            if(depth[e] != -1)
                continue;
            q.push({e,d+1});
            depth[e] = d + 1;
            edsort.pb(key[{min(node,e),max(node,e)}]);
        }
    }
    int dom[n];
    memset(dom,0,sizeof(dom));
    for(int minis = 1; minis <= m; minis ++)
    {
        vi nei;
        int s; cin>> s;
        for(int u = 1; u <= s; u ++)
        {
            int x; cin >> x;
            nei.pb(x);
        }
        //cout << "this far" << endl;
        sort(all(nei),comp);
        int u = depth[nei[0]];
        int v = depth[nei[s-1]];
        for(int j = u; j < v; j ++)
            dom[j]++;
    }
    for(int i = 0; i < n-1; i ++)
    {
        if(dom[i] >= k)
            ans.insert(edsort[i]);
    }
    cout << ans.size() << '\n';
    for(auto e: ans)
        cout << e << ' ';

}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int tt = 1;
    while(tt--)
        solve();
}
/* 6 3 2
2 5 1 5 1 3 6 3 6 4
3 2 3 4
2 1 6
3 1 6 4
*/
/*
6 3 3
1 3
2 3
3 4
6 4
4 5
2 1 3
2 6 3
2 3 2
*/

Compilation message (stderr)

railway.cpp:24:1: warning: multi-line comment [-Wcomment]
   24 | ////////////******SOLUTION******\\\\\\\\\\\
      | ^

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