Submission #148107

#	Time	Username	Problem	Language	Result	Execution time	Memory
148107		WhipppedCream	Railway (BOI17_railway)	C++17	100 / 100	353 ms	24336 KiB

railway

#include <bits/stdc++.h>
#define ii pair<int, int>
#define X first
#define Y second
#define pb push_back
#define mp make_pair
#define vi vector<int>
#define vii vector< pair<int, int> >
typedef long long ll;
using namespace std;
vii adj[100005];
vi tour;
int dat[100005];
int h[100005];
int dp[25][100005];
int marc[100005];
int toPar[100005];
int in[100005];
bool cmp(int a, int b)
{
    return dat[a] < dat[b];
}
void dfs(int u, int p)
{
    dat[u] = (int) tour.size();
    tour.pb(u);
    dp[0][u] = p;
    for(auto kk : adj[u])
    {
        int v = kk.X;
        if(v == p) continue;
        toPar[v] = kk.Y;
        h[v] = h[u]+1;
        dfs(v, u);
        in[u]++;
    }
}
int LCA(int u, int v)
{
    //printf("%d %d\n", u, v);
    if(h[u]> h[v]) swap(u, v);
    for(int i = 20; i>= 0; i--)
    {
        int xx = dp[i][v];
        if(h[xx]< h[u]) continue;
        v = xx;
    }
    if(u == v) return u;
    for(int i = 20; i>= 0; i--)
    {
        int x = dp[i][u];
        int y = dp[i][v];
        if(x == y) continue;
        u = x; v = y;
    }
    return dp[0][u];
}
void path(int a, int b)
{
    //printf("path %d %d\n", a, b);
	if(a == 0 || b == 0) return;
    marc[a]++; marc[b]++;
    int k = LCA(a, b);
    assert(k);
    marc[k] -= 2;
}
int getndtop(stack<int> &s)
{
	int x = s.top(); s.pop();
	int y = s.top(); s.push(x);
	return y;
}
int main()
{
    int n, m, k;
    scanf("%d %d %d", &n, &m, &k);
    for(int i = 0; i< n-1; i++)
    {
        int a, b; scanf("%d %d", &a, &b);
        adj[a].pb(ii(b, i+1)); adj[b].pb(ii(a, i+1));
    }
    h[1] = 1;
    dfs(1, 0);
    for(int i = 1; i<= 20; i++)
        for(int j = 1; j<= n; j++)
            dp[i][j] = dp[i-1][dp[i-1][j]];
    for(int i = 0; i< m; i++)
    {
        int xx; scanf("%d", &xx);
        vi want;
        while(xx--)
        {
            int foo; scanf("%d", &foo);
            want.pb(foo);
        }
        sort(want.begin(), want.end(), cmp);
        stack<int> s;
		s.push(0);
		int st = want[0];
		for(int j = 1; j< (int) want.size(); j++) st = LCA(st, want[j]);
		s.push(st);
		for(int j = 0; j< (int) want.size(); j++)
		{
			int u = want[j];
			int lca = LCA(u, s.top());
			if(lca == s.top())
			{
				s.push(u);
				continue;
			}
			while(LCA(getndtop(s), u) != getndtop(s))
			{
				int x = s.top(); s.pop();
				path(x, s.top());
			}
			//if(s.top() != lca)
			{
                //printf("dafuq\n");
				path(lca, s.top());
				s.pop();
				s.push(lca);
			}
			s.push(u);
		}
		while(!s.empty() && s.top())
		{
			int x = s.top(); s.pop();
			path(x, s.top());
		}
    }
    queue<int> Q;
    for(int i = 1; i<= n; i++) if(in[i] == 0) Q.push(i);
    vi ans;
    while(!Q.empty())
    {
        int x = Q.front(); Q.pop();
        if(!x) continue;
        if(marc[x]>= k) ans.pb(toPar[x]);
        marc[dp[0][x]] += marc[x];
        assert(marc[x]>= 0);
        in[dp[0][x]]--;
        if(dp[0][x] && in[dp[0][x]] == 0) Q.push(dp[0][x]);
    }
    sort(ans.begin(), ans.end());
    printf("%d\n", ans.size());
    for(auto x : ans) printf("%d ", x);
    printf("\n");
	return 0;
}

Compilation message (stderr)

railway.cpp: In function 'int main()':
railway.cpp:145: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:76: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:79:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int a, b; scanf("%d %d", &a, &b);
                   ~~~~~^~~~~~~~~~~~~~~~~
railway.cpp:89:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int xx; scanf("%d", &xx);
                 ~~~~~^~~~~~~~~~~
railway.cpp:93:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             int foo; scanf("%d", &foo);
                      ~~~~~^~~~~~~~~~~~

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