oj.uz

Submission #1066356

# Submission time Handle Problem Language Result Execution time Memory
1066356 2024-08-19T19:10:04 Z Mr_Husanboy Make them Meet (EGOI24_makethemmeet) C++17
12.5627 / 100
 50 ms 3156 KB 
//#pragma GCC optimize("Ofast,O3")
//#pragma GCC target("avx,avx2")
#include <bits/stdc++.h>
using namespace std;
 
 
 
#ifdef LOCAL
#include "debugger.cpp"
#else
#define debug(...)
#endif
template<class T>
int len(T &a){
    return a.size();
}
 
using ll = long long;
using pii = pair<int,int>;
#define all(a) (a).begin(), (a).end()
#define ff first
#define ss second
string fileio = "";
 
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
const int MOD = 1e9 + 7;
const int inf = 1e9;
const ll infl = 1e18;
const int maxn = 1e5 + 1;
 
 
 
 
 
void yesno(bool ok){
    cout << (ok ? "Yes\n" : "No\n");
}
 
 
void solve(){
    int n; cin >> n;
    int m; cin >> m;
    vector<vector<int>> g(n);
    int root = 0;
    for(int i = 0; i < m; i ++){
        int a, b; cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    for(int i = 0; i < n; i ++) if(len(g[i]) == 1){
        root = i; break;
    }

    vector<int> par(n);
    vector<int> dis(n);
    vector<int> vis(n);

    auto dfs = [&](auto &dfs, int i, int c = 0)->void{
        vis[i] = 1;
        for(auto u : g[i]){
            if(vis[u]) continue;
            dis[u] = dis[i] + 1;
            par[u] = i;
            dfs(dfs, u, c ^ 1);
        }
    };
    dfs(dfs, root);
    cout << n * (n - 1) <<'\n';

    for(int i = 0; i < (n * (n - 1)); i ++){
        for(int j = 0; j < n; j ++){
            if(j == root){
                cout << "0 "; continue;
            }
            if(dis[j] % 2 != i % 2){
                cout << dis[j] << ' ';
            }else{
                cout << dis[par[j]] << ' ';
            }
        }
        cout << '\n';
    }
}
 
int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    auto start = chrono::high_resolution_clock::now();
    #ifndef LOCAL
    if(fileio.size()){
        freopen((fileio + ".in").c_str(), "r", stdin);
        freopen((fileio + ".out").c_str(), "w", stdout);
    }
    #endif
    int testcases = 1;
    #ifdef Tests
    cin >> testcases;
    #endif
    while(testcases --){
        solve();
        if(testcases) cout << '\n';
        #ifdef LOCAL
        else cout << '\n';
        cout << "_________________________" << endl;
        #endif
    }
    #ifdef LOCAL
    auto duration = chrono::duration_cast<chrono::microseconds>(chrono::high_resolution_clock::now() - start);
    
    cout << "time: " << (double)duration.count()/1000.0 << " milliseconds" << endl;
    #endif
    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:87:10: warning: variable 'start' set but not used [-Wunused-but-set-variable]
   87 |     auto start = chrono::high_resolution_clock::now();
      |          ^~~~~
Main.cpp:90:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |         freopen((fileio + ".in").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:91:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |         freopen((fileio + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
3.694915254 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Partially correct 41 ms 2368 KB Partially correct
5 Partially correct 42 ms 2388 KB Partially correct

Subtask #2
4.8033898302 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Partially correct 1 ms 348 KB Partially correct
7 Partially correct 4 ms 604 KB Partially correct
8 Partially correct 6 ms 600 KB Partially correct
9 Partially correct 48 ms 3152 KB Partially correct

Subtask #3
4.0644067794 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Partially correct 7 ms 652 KB Partially correct
5 Partially correct 47 ms 3136 KB Partially correct
6 Partially correct 50 ms 3152 KB Partially correct
7 Partially correct 12 ms 1112 KB Partially correct

Subtask #4
0.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Partially correct 41 ms 2368 KB Partially correct
5 Partially correct 42 ms 2388 KB Partially correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Partially correct 7 ms 652 KB Partially correct
10 Partially correct 47 ms 3136 KB Partially correct
11 Partially correct 50 ms 3152 KB Partially correct
12 Partially correct 12 ms 1112 KB Partially correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Partially correct 42 ms 2384 KB Partially correct
17 Partially correct 42 ms 2384 KB Partially correct
18 Correct 0 ms 344 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Partially correct 5 ms 760 KB Partially correct
21 Partially correct 42 ms 3156 KB Partially correct
22 Partially correct 43 ms 3112 KB Partially correct
23 Partially correct 12 ms 1112 KB Partially correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Incorrect 46 ms 2440 KB If people start at 0 and 1, then they can avoid each other
28 Halted 0 ms 0 KB -

Subtask #5
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Partially correct 41 ms 2368 KB Partially correct
5 Partially correct 42 ms 2388 KB Partially correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Partially correct 1 ms 348 KB Partially correct
12 Partially correct 4 ms 604 KB Partially correct
13 Partially correct 6 ms 600 KB Partially correct
14 Partially correct 48 ms 3152 KB Partially correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Partially correct 7 ms 652 KB Partially correct
19 Partially correct 47 ms 3136 KB Partially correct
20 Partially correct 50 ms 3152 KB Partially correct
21 Partially correct 12 ms 1112 KB Partially correct
22 Correct 0 ms 344 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Partially correct 42 ms 2384 KB Partially correct
26 Partially correct 42 ms 2384 KB Partially correct
27 Correct 0 ms 344 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Partially correct 5 ms 760 KB Partially correct
30 Partially correct 42 ms 3156 KB Partially correct
31 Partially correct 43 ms 3112 KB Partially correct
32 Partially correct 12 ms 1112 KB Partially correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 0 ms 348 KB Output is correct
36 Incorrect 46 ms 2440 KB If people start at 0 and 1, then they can avoid each other
37 Halted 0 ms 0 KB -