oj.uz

Submission #582243

# Submission time Handle Problem Language Result Execution time Memory
582243 2022-06-23T14:35:11 Z jiahng Village (BOI20_village) C++14
50 / 100
 110 ms 22808 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define int ll
typedef pair<int32_t, int32_t> pi;
typedef vector <int> vi;
typedef vector <pi> vpi;
typedef pair<pi, ll> pii;
typedef set <ll> si;
typedef long double ld;
#define f first
#define s second
#define mp make_pair
#define FOR(i,s,e) for(int i=s;i<=int(e);++i)
#define DEC(i,s,e) for(int i=s;i>=int(e);--i)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
#define aFOR(i,x) for (auto i: x)
#define mem(x,i) memset(x,i,sizeof x)
#define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define maxn 100010
#define INF (ll)1e9+10
#define MOD 1000000007
typedef pair <vi, int> pvi;
typedef pair <int,pi> ipi;
typedef vector <pii> vpii;
int N,a,b,c;
vi adj[maxn];
int maxans[maxn];
vi A[maxn];
int sz[maxn], depth[maxn];
void dfs(int x,int p){
    sz[x] = 1;
    aFOR(i,adj[x]) if (i != p){
        depth[i] = depth[x] + 1;
        dfs(i,x);
        sz[x] += sz[i];
    }
}
int minans[maxn], minval = 0;
void getmin(int x,int p){
    aFOR(i,adj[x]) if (i != p){
        getmin(i,x);
        if (minans[i] == i){
           minval += 2; swap(minans[i], minans[x]);
        }
    }
    if (minans[x] == x && adj[x].size() - (p != -1) != 0){
        minval += 2;
        aFOR(i,adj[x]) if (i != p){
            swap(minans[i], minans[x]); break;
        }
    }
} 
int get_cent(int x,int p){
    aFOR(i,adj[x]) if (i != p && sz[i] > N/2) return get_cent(i,x);
    return x;
}
vi v;
void get_set(int x,int p,int y){
    v.pb(x);
    aFOR(i,adj[x]) if (i != p) get_set(i,x,y);
}
int32_t main(){
    fast;
    cin >> N;
    FOR(i,1,N-1){
        cin >> a >> b; adj[a].pb(b); adj[b].pb(a);
    }
    dfs(1,-1);
    FOR(i,1,N) minans[i] = i;
    getmin(1,-1);

    int cent = get_cent(1,-1);
    depth[cent] = 0;
    dfs(cent,-1);
    int maxval = 0;
    FOR(i,1,N) maxval += 2*min(sz[i], N - sz[i]);

    int mxsz = 1;
    aFOR(i,adj[cent]){
        get_set(i, cent, i); mxsz = max(mxsz, sz[i]);
    }
    v.pb(cent);
    vi v2;
    aFOR(i,v) v2.pb(i);
    rotate(v2.begin(), v2.begin() + mxsz, v2.end());
    FOR(i,0,v.size()-1) maxans[v[i]] = v2[i];
    
    
    cout << minval << ' ' << maxval << '\n';
    FOR(i,1,N) cout << minans[i] << ' '; cout << '\n';
    FOR(i,1,N) cout << maxans[i] << ' ';
}

Compilation message

Village.cpp: In function 'int32_t main()':
Village.cpp:15:20: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   15 | #define FOR(i,s,e) for(int i=s;i<=int(e);++i)
      |                    ^~~
Village.cpp:95:5: note: in expansion of macro 'FOR'
   95 |     FOR(i,1,N) cout << minans[i] << ' '; cout << '\n';
      |     ^~~
Village.cpp:95:42: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   95 |     FOR(i,1,N) cout << minans[i] << ' '; cout << '\n';
      |                                          ^~~~

Subtask #1
6.0 / 12.0

# Verdict Execution time Memory Grader output
1 Partially correct 3 ms 4948 KB Partially correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Partially correct 3 ms 4948 KB Partially correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 3 ms 5028 KB Output is correct
11 Partially correct 3 ms 5032 KB Partially correct
12 Partially correct 3 ms 4948 KB Partially correct
13 Correct 3 ms 4948 KB Output is correct
14 Correct 3 ms 4948 KB Output is correct
15 Correct 3 ms 5028 KB Output is correct
16 Correct 3 ms 4948 KB Output is correct
17 Partially correct 3 ms 5028 KB Partially correct

Subtask #2
19.0 / 38.0

# Verdict Execution time Memory Grader output
1 Partially correct 3 ms 5036 KB Partially correct
2 Partially correct 3 ms 5076 KB Partially correct
3 Partially correct 3 ms 5032 KB Partially correct
4 Partially correct 4 ms 5208 KB Partially correct
5 Partially correct 4 ms 5076 KB Partially correct
6 Partially correct 3 ms 5076 KB Partially correct
7 Partially correct 4 ms 5116 KB Partially correct
8 Partially correct 4 ms 5036 KB Partially correct
9 Partially correct 3 ms 5076 KB Partially correct
10 Partially correct 4 ms 5168 KB Partially correct
11 Partially correct 4 ms 5076 KB Partially correct
12 Correct 3 ms 5040 KB Output is correct
13 Correct 3 ms 5076 KB Output is correct
14 Correct 3 ms 5076 KB Output is correct
15 Correct 5 ms 5076 KB Output is correct
16 Partially correct 4 ms 5076 KB Partially correct
17 Correct 3 ms 5076 KB Output is correct
18 Correct 3 ms 5048 KB Output is correct
19 Correct 3 ms 5060 KB Output is correct
20 Correct 3 ms 5076 KB Output is correct
21 Correct 3 ms 5076 KB Output is correct
22 Correct 3 ms 5040 KB Output is correct
23 Partially correct 3 ms 5076 KB Partially correct
24 Partially correct 3 ms 5076 KB Partially correct
25 Partially correct 3 ms 5032 KB Partially correct
26 Partially correct 3 ms 5032 KB Partially correct
27 Partially correct 3 ms 5076 KB Partially correct
28 Partially correct 3 ms 5048 KB Partially correct
29 Partially correct 3 ms 5076 KB Partially correct
30 Correct 3 ms 5076 KB Output is correct

Subtask #3
25.0 / 50.0

# Verdict Execution time Memory Grader output
1 Partially correct 3 ms 4948 KB Partially correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Partially correct 3 ms 4948 KB Partially correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 3 ms 5028 KB Output is correct
11 Partially correct 3 ms 5032 KB Partially correct
12 Partially correct 3 ms 4948 KB Partially correct
13 Correct 3 ms 4948 KB Output is correct
14 Correct 3 ms 4948 KB Output is correct
15 Correct 3 ms 5028 KB Output is correct
16 Correct 3 ms 4948 KB Output is correct
17 Partially correct 3 ms 5028 KB Partially correct
18 Partially correct 3 ms 5036 KB Partially correct
19 Partially correct 3 ms 5076 KB Partially correct
20 Partially correct 3 ms 5032 KB Partially correct
21 Partially correct 4 ms 5208 KB Partially correct
22 Partially correct 4 ms 5076 KB Partially correct
23 Partially correct 3 ms 5076 KB Partially correct
24 Partially correct 4 ms 5116 KB Partially correct
25 Partially correct 4 ms 5036 KB Partially correct
26 Partially correct 3 ms 5076 KB Partially correct
27 Partially correct 4 ms 5168 KB Partially correct
28 Partially correct 4 ms 5076 KB Partially correct
29 Correct 3 ms 5040 KB Output is correct
30 Correct 3 ms 5076 KB Output is correct
31 Correct 3 ms 5076 KB Output is correct
32 Correct 5 ms 5076 KB Output is correct
33 Partially correct 4 ms 5076 KB Partially correct
34 Correct 3 ms 5076 KB Output is correct
35 Correct 3 ms 5048 KB Output is correct
36 Correct 3 ms 5060 KB Output is correct
37 Correct 3 ms 5076 KB Output is correct
38 Correct 3 ms 5076 KB Output is correct
39 Correct 3 ms 5040 KB Output is correct
40 Partially correct 3 ms 5076 KB Partially correct
41 Partially correct 3 ms 5076 KB Partially correct
42 Partially correct 3 ms 5032 KB Partially correct
43 Partially correct 3 ms 5032 KB Partially correct
44 Partially correct 3 ms 5076 KB Partially correct
45 Partially correct 3 ms 5048 KB Partially correct
46 Partially correct 3 ms 5076 KB Partially correct
47 Correct 3 ms 5076 KB Output is correct
48 Partially correct 81 ms 14996 KB Partially correct
49 Partially correct 80 ms 15960 KB Partially correct
50 Partially correct 91 ms 15940 KB Partially correct
51 Partially correct 61 ms 13568 KB Partially correct
52 Partially correct 80 ms 15788 KB Partially correct
53 Partially correct 69 ms 14692 KB Partially correct
54 Partially correct 42 ms 13680 KB Partially correct
55 Partially correct 109 ms 22808 KB Partially correct
56 Partially correct 104 ms 19368 KB Partially correct
57 Partially correct 96 ms 18048 KB Partially correct
58 Partially correct 103 ms 17004 KB Partially correct
59 Partially correct 83 ms 16056 KB Partially correct
60 Correct 50 ms 15944 KB Output is correct
61 Correct 55 ms 16188 KB Output is correct
62 Correct 59 ms 16240 KB Output is correct
63 Correct 58 ms 15584 KB Output is correct
64 Partially correct 66 ms 16372 KB Partially correct
65 Correct 70 ms 16448 KB Output is correct
66 Correct 64 ms 15536 KB Output is correct
67 Correct 42 ms 13248 KB Output is correct
68 Correct 51 ms 14724 KB Output is correct
69 Correct 67 ms 16424 KB Output is correct
70 Correct 53 ms 15672 KB Output is correct
71 Correct 39 ms 12992 KB Output is correct
72 Correct 45 ms 13996 KB Output is correct
73 Correct 61 ms 16404 KB Output is correct
74 Correct 52 ms 15424 KB Output is correct
75 Partially correct 110 ms 16400 KB Partially correct
76 Partially correct 67 ms 15728 KB Partially correct
77 Partially correct 64 ms 16052 KB Partially correct
78 Partially correct 45 ms 12568 KB Partially correct
79 Partially correct 50 ms 13636 KB Partially correct
80 Partially correct 76 ms 16352 KB Partially correct
81 Partially correct 70 ms 16276 KB Partially correct
82 Partially correct 63 ms 15988 KB Partially correct