Submission #857979

#	Time	Username	Problem	Language	Result	Execution time	Memory
857979		vjudge1	Bosses (BOI16_bosses)	C++17	0 / 100	0 ms	604 KiB

bosses

//    //In His Name
//    #include <bits/stdc++.h>
//    using namespace std;
//    #define ll long long
//    //#define int ll
//    typedef pair<int, int> pii;
//    typedef pair<long long, int> pli;
//    typedef pair<long long, long long> pll;
//    #define F first
//    #define S second
//    #define bug(x) cout << "Ah shit , here we go again : " << x <<endl
//    #define all(x) x.begin() , x.end()
//    #define pb push_back
//    const int maxn = 5e5 + 10, MOD = 1e9 + 7 , sq = 350;
//    const ll INF = 1e18;
//    struct hoom{
//        int l , r , w , index;
//    };
//
//    int n , m , c[maxn] , vt[2*maxn] , h[maxn] , st[maxn] , fn[maxn] , t = 1 , cnt[200] ;
//    bool  mark[maxn];
//    string ans[maxn];
//    vector<int> adj[maxn];
//    vector<hoom> q;
//
//    bool cmp(hoom a , hoom b){
//        return (a.l/sq != b.l/sq ?  a.l < b.l : a.r < b.r);
//    }
//
//    void dfs(int v , int p){
//        h[v] = h[p]+1;
//        st[v] = t;
//        vt[t] = v;
//        t++;
//        for(int u : adj[v]) if(u!=p) dfs(u,v);
//        fn[v] = t;
//        vt[t] = v;
//        t++;
//    }
//
//    int main(){
//        ios_base::sync_with_stdio(false);
//
//        cin >> n >> m;
//        for(int i = 2 ; i <= n ; i++){
//            int u ;
//            cin >> u;
//            adj[u].pb(i);
//            adj[i].pb(u);
//        }
//        string s;
//        cin >> s;
//        for (int i = 1; i <= n ; ++i) c[i] = int(s[i-1]);
//        dfs(1,0);
//        for(int i = 1 ; i <= m ; i++){
//            int v , k;
//            cin >> v >> k;
//            q.pb({st[v] , fn[v] , k , i});
//        }
//        sort(all(q) , cmp);
//        int L = 0 , R = 1 , x = 0;
//        for(hoom i : q){
//            int l = i.l , r = i.r , ind = i.index ;
//
//            while(R <= i.r){
//                int v = vt[R];
//                if(mark[vt[R]]){
//                    mark[vt[R]] = false;
//                }
//                else {
//                    mark[R] = true;
//                    if (h[vt[R]] == i.w) {
//                        cnt[c[vt[R]]]++;
//                        if (cnt[c[vt[R]]] % 2 == 1) x++;
//                        else x--;
//                    }
//                }
//                R++;
//            }
//            while(L-1 >= i.l){
//                L--;
//                if(mark[vt[L]]){
//                    mark[vt[L]] = false;
//                    continue;
//                }
//                else mark[vt[L]] = true;
//                if(h[vt[L]] == i.w) {
//                    cnt[c[vt[L]]]--;
//                    if (cnt[c[vt[L]]] % 2 == 1) x++;
//                    else x--;
//                }
//            }
//            while(L+1 <= i.l){
//                if(mark[vt[L]]){
//                    mark[vt[L]] = false;
//                }
//                else {
//                    mark[vt[L]] = true;
//                    if (h[vt[L]] == i.w) {
//                        cnt[c[vt[L]]]++;
//                        if (cnt[c[vt[L]]] % 2 == 1) x++;
//                        else x--;
//                    }
//                }
//                L++;
//            }
//            while(R-1 > i.r){
//                R--;
//                if(mark[vt[R]]){
//                    mark[vt[R]] = false;
//                    continue;
//                }
//                else mark[vt[R]] = true;
//                if(h[vt[R]] == i.w) {
//                    cnt[c[vt[R]]]--;
//                    if (cnt[c[vt[R]]] % 2 == 1) x++;
//                    else x--;
//                }
//            }
//            ans[i.index] = (x == 1 or x == 0 ? "YES" : "NO");
//        }
//        for(int i = 1 ; i <= m ; i++) cout << ans[i] << "\n";
//    }












//In His Name
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef pair<long long, int> pli;
typedef pair<long long, long long> pll;
#define ll long long
#define int ll
#define F first
#define S second
#define pb push_back
#define bug(x) cout << "Ah shit , here we go again : " << x <<endl
#define all(x) x.begin() , x.end()
#define ceil(x,y) x/y + min(1,x%y);
const int maxn = 5000 + 10, MOD = 1e9 + 7;
const ll INF = 1e18;

int n , h[maxn] , ans = INF , ians = 1 , cnt[maxn] , cnt2[maxn];
vector<int> adj[maxn] , adj2[maxn];
bool mark[maxn];

void dfs(int v){
    mark[v] = true;
    for(int u : adj2[v]){
        if(!mark[u]){
            dfs(u);
            h[v] += h[u];
        }
    }
}

main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    for(int i = 1 ; i <= n ; i++){
        int x;
        cin >> x;
        for(int u = 1 ; u <= x ; u++){
            int y;
            cin >> y;
            adj[y].pb(i);
        }
    }
    queue<int> q;
    for(int i = 1 ; i <= n ; i++){
        q.push(i);
        mark[i] = true;
        while(!q.empty()){
            int v = q.front();
            q.pop();
            for(int u : adj[v]){
                if(!mark[u]) {
                    q.push(u);
                    mark[u] = true;
                    h[u] = h[v]+1;
                }
            }
        }
        memset(cnt , 0 , sizeof cnt);
        int maxi = -1e9 , ok = 1 , hoom = 0;
        for(int j = 1 ; j <= n ; j++) if(!mark[j]) ok = 0;
        for(int j = 1 ; j <= n ; j++){
            cnt[h[j]]++;
        }
        for(int j = maxn ; j >= 1 ; j++){
            if(cnt[j] > cnt2[j]){
                hoom = 1;
                break;
            }
            if(cnt2[j] > cnt[j]) break;
        }
        if(hoom and ok) {
            ans = i;
            for(int j = 1 ; j < maxn ; j++) cnt2[j] = cnt[j];
        }
    }
    memset(mark , false , sizeof mark);
    fill(h , h+n+5 , 0);
    q.push(ians);
    mark[ians] = true;
    while(!q.empty()){
        int v = q.front();
        q.pop();
        for(int u : adj[v]){
            if(!mark[u]) {
                q.push(u);
                mark[u] = true;
                h[u] = h[v]+1;
                adj2[v].pb(u);
                adj2[u].pb(v);
            }
        }
    }
    memset(mark , false , sizeof mark);
    fill(h , h+n+5 , 1);
    dfs(ians);
    int sum = 0ll;
    for(int i = 1 ; i <= n ; i++) sum += h[i];
    cout << sum;
}

Compilation message (stderr)

bosses.cpp:167:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  167 | main(){
      | ^~~~
bosses.cpp: In function 'int main()':
bosses.cpp:198:13: warning: unused variable 'maxi' [-Wunused-variable]
  198 |         int maxi = -1e9 , ok = 1 , hoom = 0;
      |             ^~~~
bosses.cpp:204:21: warning: array subscript 5010 is above array bounds of 'long long int [5010]' [-Warray-bounds]
  204 |             if(cnt[j] > cnt2[j]){
      |                ~~~~~^
bosses.cpp:153:42: note: while referencing 'cnt'
  153 | int n , h[maxn] , ans = INF , ians = 1 , cnt[maxn] , cnt2[maxn];
      |                                          ^~~
bosses.cpp:204:31: warning: array subscript 5010 is above array bounds of 'long long int [5010]' [-Warray-bounds]
  204 |             if(cnt[j] > cnt2[j]){
      |                         ~~~~~~^
bosses.cpp:153:54: note: while referencing 'cnt2'
  153 | int n , h[maxn] , ans = INF , ians = 1 , cnt[maxn] , cnt2[maxn];
      |                                                      ^~~~

• Subtask 1: 0 / 22
• Subtask 2: 0 / 45
• Subtask 3: 0 / 33