oj.uz

Submission #1033976

# Submission time Handle Problem Language Result Execution time Memory
1033976 2024-07-25T08:15:08 Z vjudge1 Meetings 2 (JOI21_meetings2) C++14
4 / 100
 90 ms 10636 KB 
#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

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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10332 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Correct 2 ms 10588 KB Output is correct
4 Correct 15 ms 10632 KB Output is correct
5 Correct 16 ms 10636 KB Output is correct
6 Correct 17 ms 10632 KB Output is correct
7 Correct 19 ms 10584 KB Output is correct
8 Correct 37 ms 10628 KB Output is correct
9 Correct 64 ms 10584 KB Output is correct
10 Correct 63 ms 10584 KB Output is correct
11 Correct 64 ms 10588 KB Output is correct
12 Correct 57 ms 10584 KB Output is correct
13 Correct 90 ms 10584 KB Output is correct
14 Correct 15 ms 10584 KB Output is correct
15 Correct 15 ms 10588 KB Output is correct
16 Correct 30 ms 10636 KB Output is correct
17 Correct 71 ms 10588 KB Output is correct
18 Correct 62 ms 10584 KB Output is correct
19 Correct 29 ms 10584 KB Output is correct
20 Correct 63 ms 10588 KB Output is correct
21 Correct 29 ms 10588 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10332 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Correct 2 ms 10588 KB Output is correct
4 Correct 15 ms 10632 KB Output is correct
5 Correct 16 ms 10636 KB Output is correct
6 Correct 17 ms 10632 KB Output is correct
7 Correct 19 ms 10584 KB Output is correct
8 Correct 37 ms 10628 KB Output is correct
9 Correct 64 ms 10584 KB Output is correct
10 Correct 63 ms 10584 KB Output is correct
11 Correct 64 ms 10588 KB Output is correct
12 Correct 57 ms 10584 KB Output is correct
13 Correct 90 ms 10584 KB Output is correct
14 Correct 15 ms 10584 KB Output is correct
15 Correct 15 ms 10588 KB Output is correct
16 Correct 30 ms 10636 KB Output is correct
17 Correct 71 ms 10588 KB Output is correct
18 Correct 62 ms 10584 KB Output is correct
19 Correct 29 ms 10584 KB Output is correct
20 Correct 63 ms 10588 KB Output is correct
21 Correct 29 ms 10588 KB Output is correct
22 Incorrect 4 ms 10584 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10332 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Correct 2 ms 10588 KB Output is correct
4 Correct 15 ms 10632 KB Output is correct
5 Correct 16 ms 10636 KB Output is correct
6 Correct 17 ms 10632 KB Output is correct
7 Correct 19 ms 10584 KB Output is correct
8 Correct 37 ms 10628 KB Output is correct
9 Correct 64 ms 10584 KB Output is correct
10 Correct 63 ms 10584 KB Output is correct
11 Correct 64 ms 10588 KB Output is correct
12 Correct 57 ms 10584 KB Output is correct
13 Correct 90 ms 10584 KB Output is correct
14 Correct 15 ms 10584 KB Output is correct
15 Correct 15 ms 10588 KB Output is correct
16 Correct 30 ms 10636 KB Output is correct
17 Correct 71 ms 10588 KB Output is correct
18 Correct 62 ms 10584 KB Output is correct
19 Correct 29 ms 10584 KB Output is correct
20 Correct 63 ms 10588 KB Output is correct
21 Correct 29 ms 10588 KB Output is correct
22 Incorrect 4 ms 10584 KB Output isn't correct
23 Halted 0 ms 0 KB -