Submission #208540

#	Time	Username	Problem	Language	Result	Execution time	Memory
208540		eriksuenderhauf	Railway (BOI17_railway)	C++11	100 / 100	132 ms	28532 KiB

railway

//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define enl printf("\n")
#define case(t) printf("Case #%d: ", (t))
#define ni(n) scanf("%d", &(n))
#define nl(n) scanf("%lld", &(n))
#define nai(a, n) for (int i = 0; i < (n); i++) ni(a[i])
#define nal(a, n) for (int i = 0; i < (n); i++) nl(a[i])
#define pri(n) printf("%d\n", (n))
#define prl(n) printf("%lld\n", (n))
#define pii pair<int, int>
#define pil pair<int, long long>
#define pll pair<long long, long long>
#define vii vector<pii>
#define vil vector<pil>
#define vll vector<pll>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef cc_hash_table<int,int,hash<int>> ht;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> oset;
const double pi = acos(-1);
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
const int MAXN = 3e5 + 5;
const double eps = 1e-9;
int U[MAXN], V[MAXN], disc[MAXN], cnt[MAXN];
int t = 0, par[17][MAXN], depth[MAXN];
vi adj[MAXN];

void dfs(int u, int p) {
    disc[u] = t++;
    for (int v: adj[u]) {
        if (v == p) continue;
        par[0][v] = u;
        depth[v] = depth[u] + 1;
        dfs(v, u);
    }
}

int lca(int u, int v) {
    if (depth[u] > depth[v])
        swap(u, v);
    int d = depth[v] - depth[u];
    for (int i = 0; i < 17; i++)
        if ((d >> i) & 1)
            v = par[i][v];
    if (u == v) return u;
    for (int i = 16; i > -1; i--)
        if (par[i][u] != par[i][v])
            u = par[i][u], v = par[i][v];
    return par[0][u];
}

void dfs2(int u, int p) {
    for (int v: adj[u]) {
        if (v == p)
            continue;
        dfs2(v, u);
        cnt[u] += cnt[v];
    }
}

int main() {
    int n, m, k;
    scanf("%d %d %d", &n, &m, &k);
    for (int i = 1; i < n; i++) {
        scanf("%d %d", &U[i], &V[i]);
        U[i]--, V[i]--;
        adj[U[i]].pb(V[i]);
        adj[V[i]].pb(U[i]);
    }
    depth[0] = 0;
    dfs(0, -1);
    for (int i = 1; i < 17; i++)
        for (int j = 0; j < n; j++)
            par[i][j] = par[i - 1][par[i - 1][j]];
    for (int i = 0; i < m; i++) {
        vector<int> cur;
        int s;
        scanf("%d", &s);
        for (int j = 0; j < s; j++) {
            int u;
            scanf("%d", &u);
            cur.pb(--u);
        }
        sort(cur.begin(), cur.end(), [](int u, int v){
            return disc[u] < disc[v];
        });
        for (int j = 0; j < s; j++) {
            int l = lca(cur[j], cur[(j+1)%s]);
            cnt[l] -= 2;
            cnt[cur[j]]++, cnt[cur[(j+1)%s]]++;
        }
    }
    dfs2(0, -1);
    vi ans;
    for (int i = 1; i < n; i++) {
        if (disc[U[i]] < disc[V[i]])
            swap(U[i], V[i]);
        if (cnt[U[i]] >= 2 * k)
            ans.pb(i);
    }
    printf("%d\n", ans.size());
    for (int i: ans)
        printf("%d ", i);
    printf("\n");
}

Compilation message (stderr)

railway.cpp: In function 'int main()':
railway.cpp:112:30: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
     printf("%d\n", ans.size());
                    ~~~~~~~~~~^
railway.cpp:74:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &n, &m, &k);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
railway.cpp:76:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &U[i], &V[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
railway.cpp:89:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &s);
         ~~~~~^~~~~~~~~~
railway.cpp:92:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &u);
             ~~~~~^~~~~~~~~~

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