Submission #282025

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
282025	2020-08-23T19:50:39 Z	JoMee	Railway (BOI17_railway)	C++17	7 / 100	1000 ms	67320 KB

railway

#include <bits/stdc++.h>

#define int long long

using namespace std;

#define rep(i,a,n) for(int i = a; i<n; i++)
#define per(i,a,n) for(int i = n-1; i>=a; i--)

int max(int a,int b){return (a>b)?a:b;}
int min(int a,int b){return (a<b)?a:b;}

vector<int> adj[100000];
int par[20][100000], szs[100000], depth[100000];
set<int> start[100000];
set<int> out[100000];
pair<int,int> edges[100000];

void dfs(int e,int p){
    par[0][e] = p;
    depth[e] = depth[p]+1;
    for(int j:adj[e]){
        if(j != p)dfs(j,e);
    }
}
set<int>* smldfs(int i,int p){
    set<int>* ret = new set<int>(start[i].begin(),start[i].end());
    for(auto e:adj[i]){
        if(e != p){
            set<int>* v = smldfs(e,i);
            if(v->size() > ret->size())swap(v,ret);
            for(auto f:(*v)){
                ret->insert(f);
            }

        }
    }
    for(auto f:out[i]){
        ret->erase(f);
    }
    szs[i] = ret->size();
    return ret;
}
int moveUp(int idx,int d){
    for(int i = 0; d > 0; i++){
        if(d&1)idx = par[i][idx];
        d/=2;
    }
    return idx;
}

int lca(int a,int b){
    if(depth[a] < depth[b])swap(a,b);

    a = moveUp(a,depth[a]-depth[b]);
    if(a == b)return a;
    for(int i = 20; i >= 0; i++){
        if(par[i][a] != par[i][b]){
            a = par[i][a];
            b = par[i][b];
        }
    }
    return par[0][a];
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n,k,m;
    cin>>n>>m>>k;
    rep(i,0,n-1){
        int a,b;
        cin>>a>>b;a--;b--;
        adj[a].push_back(b);
        adj[b].push_back(a);
        edges[i] = make_pair(a,b);
    }
    memset(szs,0,sizeof(szs));
    depth[0] = -1;
    dfs(0,0);
    rep(i,1,20)rep(j,0,100000)par[i][j] = par[i-1][par[i-1][j]];
    rep(i,0,m){
        int x;
        cin>>x;
        int la = -1;

        rep(j,0,x){
            int k;
            cin>>k;k--;
            start[k].insert(i);

            if(la == -1)la = k;
            else{
                la = lca(la,k);
            }
        }
        out[la].insert(i);

    }
    smldfs(0,0);
    vector<int> ans;
    rep(i,0,n-1){
        int a = (depth[edges[i].first] > depth[edges[i].second])?edges[i].first:edges[i].second;
        if(szs[a] >= k)ans.push_back(i+1);
    }
    cout<<ans.size()<<"\n";
    for(auto i:ans)cout<<i<<" ";
    cout<<"\n";
}

Compilation message

railway.cpp: In function 'long long int lca(long long int, long long int)':
railway.cpp:57:5: warning: iteration 9223372036854775787 invokes undefined behavior [-Waggressive-loop-optimizations]
   57 |     for(int i = 20; i >= 0; i++){
      |     ^~~
railway.cpp:57:23: note: within this loop
   57 |     for(int i = 20; i >= 0; i++){
      |                     ~~^~~~

Subtask #1
0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1062 ms	27776 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1062 ms	27776 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #3
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	249 ms	65348 KB	Output is correct
2	Correct	18 ms	27776 KB	Output is correct
3	Correct	238 ms	64516 KB	Output is correct
4	Correct	232 ms	64352 KB	Output is correct
5	Correct	200 ms	62444 KB	Output is correct
6	Correct	192 ms	67320 KB	Output is correct