oj.uz

Submission #1033732

# Submission time Handle Problem Language Result Execution time Memory
1033732 2024-07-25T04:35:27 Z vjudge1 Bitaro, who Leaps through Time (JOI19_timeleap) C++14
0 / 100
 12 ms 19548 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

timeleap.cpp: In function 'int main()':
timeleap.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);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
timeleap.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
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 12 ms 19544 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 11 ms 19548 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 66.0

# Verdict Execution time Memory Grader output
1 Runtime error 12 ms 19544 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -