oj.uz

Submission #45177

# Submission time Handle Problem Language Result Execution time Memory
45177 2018-04-11T16:00:25 Z ikura355 Library (JOI18_library) C++14
19 / 100
 2000 ms 1384 KB 
#include "library.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 5;
int n;
int tree[maxn*4];
vector<int> vec;
vector<int> way[maxn];
vector<int> ans;
void build(int pos, int l, int r) {
    if(l>r) return ;
    tree[pos] = Query(vec);
//    printf("build %d: %d %d = %d\n",pos,l,r,tree[pos]);
    if(l==r) return ;
    int mid = (l+r)/2;
    for(int i=mid+1;i<=r;i++) vec[i-1] = 0;
    build(pos<<1,l,mid);
    for(int i=mid+1;i<=r;i++) vec[i-1] = 1;
    for(int i=l;i<=mid;i++) vec[i-1] = 0;
    build(pos<<1|1,mid+1,r);
    for(int i=l;i<=mid;i++) vec[i-1] = 1;
}
void link(int pos, int l, int r, int x) {
    if(l>r || x<=l) return ;
    vec[x-1] = 1;
//    printf("link [%d, %d] : %d\n",l,r,Query(vec));
    if(Query(vec) > tree[pos]) return ;
    if(l==r) {
//        printf("----- link %d : %d\n",l,x);
        way[l].push_back(x);
        way[x].push_back(l);
        return ;
    }
    int mid = (l+r)/2;
    for(int i=mid+1;i<=r;i++) vec[i-1] = 0;
    link(pos<<1,l,mid,x);
    for(int i=mid+1;i<=r;i++) vec[i-1] = 1;
    for(int i=l;i<=mid;i++) vec[i-1] = 0;
    link(pos<<1|1,mid+1,r,x);
    for(int i=l;i<=mid;i++) vec[i-1] = 1;
}
void dfs(int u, int last) {
    ans.push_back(u);
    for(auto v : way[u]) {
        if(v==last) continue;
        dfs(v, u);
    }
}
void Solve(int N) {
    n = N;
    for(int i=1;i<=n;i++) vec.push_back(1);
    build(1,1,n);
//    if(n>200) return ;
    if(n==1) {
        Answer({1});
        return ;
    }
    for(int i=1;i<=n;i++) link(1,1,n,i);
    for(int i=1;i<=n;i++) {
        if(way[i].size()==1) {
            dfs(i, 0);
            Answer(ans);
            return ;
        }
    }
}

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 376 KB Output is correct
2 Correct 66 ms 376 KB Output is correct
3 Correct 74 ms 572 KB Output is correct
4 Correct 95 ms 572 KB Output is correct
5 Correct 55 ms 644 KB Output is correct
6 Correct 83 ms 644 KB Output is correct
7 Correct 73 ms 652 KB Output is correct
8 Correct 73 ms 652 KB Output is correct
9 Correct 73 ms 652 KB Output is correct
10 Correct 40 ms 652 KB Output is correct
11 Correct 2 ms 652 KB Output is correct
12 Correct 2 ms 652 KB Output is correct
13 Correct 2 ms 652 KB Output is correct
14 Correct 2 ms 652 KB Output is correct
15 Correct 3 ms 652 KB Output is correct
16 Correct 8 ms 652 KB Output is correct

Subtask #2
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 376 KB Output is correct
2 Correct 66 ms 376 KB Output is correct
3 Correct 74 ms 572 KB Output is correct
4 Correct 95 ms 572 KB Output is correct
5 Correct 55 ms 644 KB Output is correct
6 Correct 83 ms 644 KB Output is correct
7 Correct 73 ms 652 KB Output is correct
8 Correct 73 ms 652 KB Output is correct
9 Correct 73 ms 652 KB Output is correct
10 Correct 40 ms 652 KB Output is correct
11 Correct 2 ms 652 KB Output is correct
12 Correct 2 ms 652 KB Output is correct
13 Correct 2 ms 652 KB Output is correct
14 Correct 2 ms 652 KB Output is correct
15 Correct 3 ms 652 KB Output is correct
16 Correct 8 ms 652 KB Output is correct
17 Execution timed out 2074 ms 1384 KB Time limit exceeded
18 Halted 0 ms 0 KB -