Submission #1033976

#	Time	Username	Problem	Language	Result	Execution time	Memory
1033976		vjudge1	Meetings 2 (JOI21_meetings2)	C++14	4 / 100	90 ms	10636 KiB

meetings2

#define COPYRIGHT CODE BY TRINH TUAN NGHIA
#include<bits/stdc++.h>
#define Boost ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define ll long long
#define endl "\n"
#define st first
#define nd second
#define ii pair <ll,ll>
#define iii pair <ll,ii>
#define iiii pair <ii,ii>
#define pb push_back
#define NAME "city"
using namespace std;
const int N = 2e5 + 10;
const int Ns = 4e3 + 10;
int n;
vector<int> adj[N];
bool visited[N];
int ds1[Ns][Ns];
int res[N];
vector<ll> V[N];
void inp (){
    cin >> n;
    for (int i = 1; i < n; ++i){
        int u, v;
        cin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
}
void BFS(int st){
    queue<int> q;
    q.push(st);
    while (!q.empty()){
        int u = q.front();
        visited[u] = true;
        q.pop();
        for(auto v : adj[u]){
            if (!visited[v]){
                visited[v] = true;
                ds1[st][v] = ds1[st][u] + 1;
                q.push(v);
            }
        }
    }
}
void sub1(){
    for (int mask = 0; mask < (1 << n); ++mask){
        int num = 0;
        vector<int> pre;
        for (int i = 1; i <= n; ++i){
            for (int j =1 ; j <= n; ++j){
                ds1[i][j] = 0;
            }
        }
        for (int i = 0; i < n; ++i){
            if (mask & (1 << i)){
                ++num;
                pre.pb(i + 1);
            }
        }
        for (auto x : pre){
            for (int i = 1; i <= n; ++i)visited[i] = false;
            BFS(x);
        }
        ll mn = 3e18;
        int cnt = 0;
        for (int x = 1; x <= n; ++x){
            ll sum = 0;
            for (auto v : pre){
                sum += ds1[v][x];
            }
            if (sum < mn){
                mn = sum;
                cnt = 1;
            }
            else if (sum == mn){
                ++cnt;
            }
        }
        res[num] = max(res[num], cnt);
    }
    for (int i = 1; i <= n; ++i){
        cout << res[i] << endl;
    }
}
bool trigsub3(){
    for (int i = 1; i <= n; ++i){
        if (adj[i].size()> 2)return false;
    }
    return true;
}
void sub3(){
    for (int i =1 ; i <= n; ++i){
        if (i % 2 == 1){
            cout << 1 << endl;
        }
        else {
            cout << n - i + 2 << endl;
        }
    }
}
void sub2(){
    ll s[Ns];
    for (int i = 1; i <= n; ++i){
        for (int j =1 ; j <= n; ++j){
            visited[j] = false;
        }
        BFS(i);
        for (int j = 1; j <= n; ++j){
            V[i].pb(ds1[i][j]);
        }
        sort(V[i].begin(), V[i].end());
    }
    for (int k = 1; k <= n; ++k){
        ll mn = 3e18;
        int cnt = 1;
        for (int x = 1; x <= n; ++x){
            s[x] += V[x][k - 1];
            if (k == 1)cout <<"dcm " <<  s[x] << endl;
            if (s[x] < mn){
                mn = s[x];
                cnt = 1;
            }
            else if (s[x] == mn){
                ++cnt;
            }
        }
        cout << cnt << endl;
    }
}
void solve(){
    if (n <= 16){
        sub1();
        return;
    }
    if (trigsub3()){
        sub3();
        return;
    }
//    sub2();

}
signed main (){
    if (fopen(NAME".inp", "r")){
        freopen(NAME".inp", "r", stdin);
        freopen(NAME".out", "w", stdout);
    }
    Boost;
    inp();
    solve();
}
/*
input

*/

/*
output

*/

Compilation message (stderr)

meetings2.cpp: In function 'int main()':
meetings2.cpp:146:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  146 |         freopen(NAME".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
meetings2.cpp:147:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  147 |         freopen(NAME".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 0 / 16
• Subtask 3: 0 / 80