Submission #1099486

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099486		Niosakaru	Railway (BOI17_railway)	Java	Compilation error	0 ms	0 KiB

This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.

railway

#include <bits/stdc++.h>
 
using namespace std;
 
#define int long long
#define mp make_pair
#define ii pair <int,int>
 
const int N = 1e5 + 5 , Lg = 17;
 
int n , m , k , u , v , P , T , Roto , in[N] , d[N] , x[N] , dp[N] , p[N][Lg] , cnt[N];
vector <ii> adj[N];
vector <int> rt , qu[N];
 
void dfs(int u){
    in[u] = ++ T;
    for (int i = 1 ; i < Lg ; i ++) p[u][i] = p[p[u][i-1]][i-1];
    for (auto i : adj[u]) if (i.first != p[u][0])
    {
        p[i.first][0] = u , d[i.first] = d[u] + 1;
        dfs(i.first);
    }
}
 
int __lca(int u,int v){
    if (d[u] < d[v]) swap(u,v);
    for (int i = Lg - 1 ; i >= 0 ; i --) if (d[p[u][i]] >= d[v]) u = p[u][i];
    if (u == v) return u;
    for (int i = Lg - 1 ; i >= 0 ; i --) if (p[u][i] != p[v][i]) u = p[u][i] , v = p[v][i];
    return p[u][0];
}
 
bool cmp(int& a,int& b){
    return in[a] < in[b];
}
 
void calc(int u){
    for (int j = 0 ; j < (int)adj[u].size() ; j ++){
        int v = adj[u][j].first , i = adj[u][j].second;
        if (v == p[u][0]) continue;
        calc(v) , cnt[i] = dp[v] , dp[u] += dp[v];
    }
}
 
signed main(){
    cin.tie(0)->sync_with_stdio(0);
 
    cin >> n >> m >> k;
    for (int i = 1 ; i < n ; i ++) cin >> u >> v , adj[u].push_back(mp(v,i)) , adj[v].push_back(mp(u,i));
    
    dfs(1);
  	int cn = 1;
    for (int i = 1 ; i <= m ; i ++){
        cin >> x[i];
        cn &= x[i] == 2;
      	qu[i].resize(x[i]);
        for (int j = 0 ; j < x[i] ; j ++) cin >> qu[i][j];
        sort(qu[i].begin() , qu[i].end() , cmp);
    }
  
  	if (cn){
		for (int i = 1 ; i <= m ; i ++){
          	u = qu[i][0] , v = qu[i][1];
          	P = __lca(u,v);
          	dp[u] ++ , dp[v] ++;
          	dp[P] --;
        }
      	    calc(1);
    for (int i = 1 ; i < n ; i ++) if (cnt[i] >= k) rt.push_back(i);
    cout << rt.size() << '\n';
    sort(rt.begin() , rt.end());
    for (auto u : rt) cout << u << ' ';
      return 0;
    }
  
  	for (int i = 1 ; i <= m ; i ++){
        Roto = qu[i][0];
        for (int j = 1 ; j < x[i] ; j ++){
            P = __lca(qu[i][j-1] , qu[i][j]);
            dp[qu[i][j]] ++ , dp[P] --;
            if (d[Roto] > d[P]) dp[Roto] ++ , dp[P] -- , Roto = P;
        }
    }
  
    calc(1);
    for (int i = 1 ; i < n ; i ++) if (cnt[i] >= k) rt.push_back(i);
    cout << rt.size() << '\n';
    sort(rt.begin() , rt.end());
    for (auto u : rt) cout << u << ' ';
 
    return 0;
}

Compilation message (stderr)

railway.java:1: error: illegal character: '#'
#include <bits/stdc++.h>
^
railway.java:1: error: class, interface, or enum expected
#include <bits/stdc++.h>
         ^
railway.java:5: error: illegal character: '#'
#define int long long
^
railway.java:5: error: class, interface, or enum expected
#define int long long
        ^
railway.java:6: error: illegal character: '#'
#define mp make_pair
^
railway.java:7: error: illegal character: '#'
#define ii pair <int,int>
^
railway.java:11: error: class, interface, or enum expected
int n , m , k , u , v , P , T , Roto , in[N] , d[N] , x[N] , dp[N] , p[N][Lg] , cnt[N];
^
railway.java:12: error: class, interface, or enum expected
vector <ii> adj[N];
^
railway.java:13: error: class, interface, or enum expected
vector <int> rt , qu[N];
^
railway.java:15: error: class, interface, or enum expected
void dfs(int u){
^
railway.java:17: error: class, interface, or enum expected
    for (int i = 1 ; i < Lg ; i ++) p[u][i] = p[p[u][i-1]][i-1];
    ^
railway.java:17: error: class, interface, or enum expected
    for (int i = 1 ; i < Lg ; i ++) p[u][i] = p[p[u][i-1]][i-1];
                     ^
railway.java:17: error: class, interface, or enum expected
    for (int i = 1 ; i < Lg ; i ++) p[u][i] = p[p[u][i-1]][i-1];
                              ^
railway.java:18: error: class, interface, or enum expected
    for (auto i : adj[u]) if (i.first != p[u][0])
    ^
railway.java:21: error: class, interface, or enum expected
        dfs(i.first);
        ^
railway.java:22: error: class, interface, or enum expected
    }
    ^
railway.java:27: error: class, interface, or enum expected
    for (int i = Lg - 1 ; i >= 0 ; i --) if (d[p[u][i]] >= d[v]) u = p[u][i];
    ^
railway.java:27: error: class, interface, or enum expected
    for (int i = Lg - 1 ; i >= 0 ; i --) if (d[p[u][i]] >= d[v]) u = p[u][i];
                          ^
railway.java:27: error: class, interface, or enum expected
    for (int i = Lg - 1 ; i >= 0 ; i --) if (d[p[u][i]] >= d[v]) u = p[u][i];
                                   ^
railway.java:28: error: class, interface, or enum expected
    if (u == v) return u;
    ^
railway.java:29: error: class, interface, or enum expected
    for (int i = Lg - 1 ; i >= 0 ; i --) if (p[u][i] != p[v][i]) u = p[u][i] , v = p[v][i];
    ^
railway.java:29: error: class, interface, or enum expected
    for (int i = Lg - 1 ; i >= 0 ; i --) if (p[u][i] != p[v][i]) u = p[u][i] , v = p[v][i];
                          ^
railway.java:29: error: class, interface, or enum expected
    for (int i = Lg - 1 ; i >= 0 ; i --) if (p[u][i] != p[v][i]) u = p[u][i] , v = p[v][i];
                                   ^
railway.java:30: error: class, interface, or enum expected
    return p[u][0];
    ^
railway.java:31: error: class, interface, or enum expected
}
^
railway.java:35: error: class, interface, or enum expected
}
^
railway.java:38: error: class, interface, or enum expected
    for (int j = 0 ; j < (int)adj[u].size() ; j ++){
                     ^
railway.java:38: error: class, interface, or enum expected
    for (int j = 0 ; j < (int)adj[u].size() ; j ++){
                                              ^
railway.java:40: error: class, interface, or enum expected
        if (v == p[u][0]) continue;
        ^
railway.java:41: error: class, interface, or enum expected
        calc(v) , cnt[i] = dp[v] , dp[u] += dp[v];
        ^
railway.java:42: error: class, interface, or enum expected
    }
    ^
railway.java:48: error: class, interface, or enum expected
    cin >> n >> m >> k;
    ^
railway.java:49: error: class, interface, or enum expected
    for (int i = 1 ; i < n ; i ++) cin >> u >> v , adj[u].push_back(mp(v,i)) , adj[v].push_back(mp(u,i));
    ^
railway.java:49: error: class, interface, or enum expected
    for (int i = 1 ; i < n ; i ++) cin >> u >> v , adj[u].push_back(mp(v,i)) , adj[v].push_back(mp(u,i));
                     ^
railway.java:49: error: class, interface, or enum expected
    for (int i = 1 ; i < n ; i ++) cin >> u >> v , adj[u].push_back(mp(v,i)) , adj[v].push_back(mp(u,i));
                             ^
railway.java:51: error: class, interface, or enum expected
    dfs(1);
    ^
railway.java:52: error: class, interface, or enum expected
  	int cn = 1;
  	^
railway.java:53: error: class, interface, or enum expected
    for (int i = 1 ; i <= m ; i ++){
    ^
railway.java:53: error: class, interface, or enum expected
    for (int i = 1 ; i <= m ; i ++){
                     ^
railway.java:53: error: class, interface, or enum expected
    for (int i = 1 ; i <= m ; i ++){
                              ^
railway.java:55: error: class, interface, or enum expected
        cn &= x[i] == 2;
        ^
railway.java:56: error: class, interface, or enum expected
      	qu[i].resize(x[i]);
      	^
railway.java:57: error: class, interface, or enum expected
        for (int j = 0 ; j < x[i] ; j ++) cin >> qu[i][j];
        ^
railway.java:57: error: class, interface, or enum expected
        for (int j = 0 ; j < x[i] ; j ++) cin >> qu[i][j];
                         ^
railway.java:57: error: class, interface, or enum expected
        for (int j = 0 ; j < x[i] ; j ++) cin >> qu[i][j];
                                    ^
railway.java:58: error: class, interface, or enum expected
        sort(qu[i].begin() , qu[i].end() , cmp);
        ^
railway.java:59: error: class, interface, or enum expected
    }
    ^
railway.java:62: error: class, interface, or enum expected
		for (int i = 1 ; i <= m ; i ++){
		                 ^
railway.java:62: error: class, interface, or enum expected
		for (int i = 1 ; i <= m ; i ++){
		                          ^
railway.java:64: error: class, interface, or enum expected
          	P = __lca(u,v);
          	^
railway.java:65: error: class, interface, or enum expected
          	dp[u] ++ , dp[v] ++;
          	^
railway.java:66: error: class, interface, or enum expected
          	dp[P] --;
          	^
railway.java:67: error: class, interface, or enum expected
        }
        ^
railway.java:69: error: class, interface, or enum expected
    for (int i = 1 ; i < n ; i ++) if (cnt[i] >= k) rt.push_back(i);
    ^
railway.java:69: error: class, interface, or enum expected
    for (int i = 1 ; i < n ; i ++) if (cnt[i] >= k) rt.push_back(i);
                     ^
railway.java:69: error: class, interface, or enum expected
    for (int i = 1 ; i < n ; i ++) if (cnt[i] >= k) rt.push_back(i);
                             ^
railway.java:70: error: class, interface, or enum expected
    cout << rt.size() << '\n';
    ^
railway.java:71: error: class, interface, or enum expected
    sort(rt.begin() , rt.end());
    ^
railway.java:72: error: class, interface, or enum expected
    for (auto u : rt) cout << u << ' ';
    ^
railway.java:73: error: class, interface, or enum expected
      return 0;
      ^
railway.java:74: error: class, interface, or enum expected
    }
    ^
railway.java:76: error: class, interface, or enum expected
  	for (int i = 1 ; i <= m ; i ++){
  	                 ^
railway.java:76: error: class, interface, or enum expected
  	for (int i = 1 ; i <= m ; i ++){
  	                          ^
railway.java:78: error: class, interface, or enum expected
        for (int j = 1 ; j < x[i] ; j ++){
        ^
railway.java:78: error: class, interface, or enum expected
        for (int j = 1 ; j < x[i] ; j ++){
                         ^
railway.java:78: error: class, interface, or enum expected
        for (int j = 1 ; j < x[i] ; j ++){
                                    ^
railway.java:80: error: class, interface, or enum expected
            dp[qu[i][j]] ++ , dp[P] --;
            ^
railway.java:81: error: class, interface, or enum expected
            if (d[Roto] > d[P]) dp[Roto] ++ , dp[P] -- , Roto = P;
            ^
railway.java:82: error: class, interface, or enum expected
        }
        ^
railway.java:86: error: class, interface, or enum expected
    for (int i = 1 ; i < n ; i ++) if (cnt[i] >= k) rt.push_back(i);
    ^
railway.java:86: error: class, interface, or enum expected
    for (int i = 1 ; i < n ; i ++) if (cnt[i] >= k) rt.push_back(i);
                     ^
railway.java:86: error: class, interface, or enum expected
    for (int i = 1 ; i < n ; i ++) if (cnt[i] >= k) rt.push_back(i);
                             ^
railway.java:87: error: class, interface, or enum expected
    cout << rt.size() << '\n';
    ^
railway.java:88: error: class, interface, or enum expected
    sort(rt.begin() , rt.end());
    ^
railway.java:89: error: class, interface, or enum expected
    for (auto u : rt) cout << u << ' ';
    ^
railway.java:91: error: class, interface, or enum expected
    return 0;
    ^
railway.java:92: error: class, interface, or enum expected
}
^
77 errors