Submission #210483

#	Time	Username	Problem	Language	Result	Execution time	Memory
210483		bash	Railway (BOI17_railway)	C++17	100 / 100	164 ms	46964 KiB

railway

/**
SXR0aXAkI0JwbXptI3FhI3Z3I293bCNqY2IjUG0jMCNicG0jVHFkcXZvLyNCcG0jQW10bjBhY2phcWFicXZvLyNNYm16dml0MSNWdyNhdGN1am16I2tpdiNhbXF9bSNQcXUjVnd6I0F0bW14MSNQcWEjaXptI2l0dCNicHF2b2EjUXYjYnBtI3BtaWRtdmEjaXZsI3d2I21pemJwMSNFcHcjcWEjYnBtem0ja2l2I3F2Ym16a21sbSNRdiNQcWEjeHptYW12a20jbXtrbXhiI0lhI3BtI3htenVxYmJtYnBHI1BtI3N2d2VtYnAjRXBpYiMraXh4bWl6bWJwI2J3I1BxYSNrem1pYmN6bWEjSWEsI0ptbnd6bSN3eiNJbmJteiN3eiNKbXBxdmwjYnBtdTEjVnd6I2FwaXR0I2JwbXwja3d1eGlhYSNJY29wYiN3biNwcWEjc3Z3ZXRtbG9tI017a214YiNpYSNQbSNlcXR0bWJwMSNQcWEjYnB6d3ZtI2x3YnAjbXtibXZsI1dkbXojYnBtI3BtaWRtdmEjSXZsI3d2I21pemJwLyNpdmwjUG0jbm1tdG1icCNWdyNuaWJxb2NtI3F2I29jaXpscXZvI0l2bCN4em1hbXpkcXZvI2JwbXUvI053eiNQbSNxYSNicG0jVXdhYiNQcW9wMSNCcG0jQWN4em11bSMrcXYjb3R3enwsMQ==
*/
#include <cstring>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <queue>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cassert>
 
#define F first
#define S second
#define endl '\n'
#define deb(x) cout<<#x<<' '<<x<<endl;
#define pb push_back
 using namespace __gnu_pbds;
using namespace std;

typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
/*
#ifdef IZI_KATKA
#define int __int64_t
#else
#define int __int64
#endif
*/
const long long MOD = 1e9 + 7;
const long long MAXN = 1e6 + 1;

typedef long long ll;

#define pii pair<int,int>
 
long long readInt() {
    bool minus1 = false;
    long long result = 0;
    char ch;
    ch = getchar();
    while (true) {
        if (ch == '-') break;
        if (ch >= '0' && ch <= '9') break;
        ch = getchar();
    }
    if (ch == '-') minus1 = true; else result = ch-'0';
    while (true) {
        ch = getchar();
        if (ch < '0' || ch > '9') break;
        result = result*10 + (ch - '0');
    }
    if (minus1)
        return -result;
    else
        return result;
}

int deg[MAXN];
int up[MAXN][22];
int cnt[MAXN];
int timer = 0;
int u[MAXN];
int v[MAXN];
int tin[MAXN];
vector<int> g[MAXN];

void dfs(int v, int par = 0) {
	deg[v] = deg[par] + 1;
	up[v][0] = par;
	timer++;
	tin[v] = timer;
	for (int i = 1; i <= 20; i++) {
		up[v][i] = up[up[v][i-1]][i-1];
	}
	for (int j : g[v]) {
		if (j == par) continue;
		dfs(j, v);
	}
}

int lca(int a, int b) {
    if (deg[a] > deg[b]) swap(a, b);
    for (int i = 20; i >= 0; i--) {
        if (deg[up[b][i]] >= deg[a]) {
            b = up[b][i];
        }
    }
    if (a == b) return a;
    for (int i = 20; i >= 0; i--) {
        if (up[b][i] != up[a][i]) {
            a = up[a][i];
            b = up[b][i];
        }
    }
    return up[a][0];
}

void add(int x, int y) {
	cnt[x]++;
	cnt[y]++;
	cnt[lca(x, y)] -= 2;
}
void dfs2(int v, int par = 0) {
	for(int j : g[v]) {
		if (j == par) continue;
		dfs2(j, v);
		cnt[v] += cnt[j];			
	}
}
bool cmp(const int &i, const int &j) {
	return tin[i] < tin[j];
}
 
int main() {
	#ifdef IZI_KATKA
	assert(freopen("input", "r", stdin));
    assert(freopen("output", "w", stdout));
    #endif
    int n = readInt(), m = readInt(), k = readInt();
    for (int i = 1; i < n; i++) {
		u[i] = readInt(), v[i] = readInt();
		g[u[i]].pb(v[i]);
		g[v[i]].pb(u[i]);
    }
    dfs(1);
    for (int i = 1; i <= m; i++) {
		int sz = readInt();
		vector<int> tmp;
		for (int j = 1; j <= sz; j++) {
			tmp.pb(readInt());
		}    	
		sort(tmp.begin(), tmp.end(), cmp);
		for (int j = 0; j < tmp.size(); j++) {
			add(tmp[j], tmp[(j + 1) % tmp.size()]);
		}
    }
    dfs2(1);
	vector<int> ans;
	for (int i = 1; i < n; i++) {
		if (tin[u[i]] > tin[v[i]]) swap(u[i], v[i]);
		if (cnt[v[i]] >= 2 * k) ans.pb(i);	
	}
	cout << ans.size() << endl;
	for (int i : ans) {
		cout << i << ' ';
	}
	return 0;
}

Compilation message (stderr)

railway.cpp: In function 'int main()':
railway.cpp:154:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < tmp.size(); j++) {
                   ~~^~~~~~~~~~~~

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