oj.uz

Submission #428650

# Submission time Handle Problem Language Result Execution time Memory
428650 2021-06-15T13:31:01 Z lyc Park (JOI17_park) C++14
77 / 100
 263 ms 672 KB 
#include "park.h"

#include <bits/stdc++.h>
using namespace std;

#define TRACE(x) cerr << #x << " :: " << x << endl
#define _ << " " <<
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for(int i=(a);i>=(b);--i)

static int Place[1400];

const int mxN = 1405;
vector<int> ans, rem, al[mxN], preorder, path;
int pa[mxN], solved[mxN];

void myans(int i, int j) {
    if (i > j) swap(i,j);
    al[i].push_back(j);
    al[j].push_back(i);
    Answer(i,j);
}

bool myask(int i, int j, vector<int> v) {
    if (i > j) swap(i,j);
    v.push_back(i);
    v.push_back(j);

    for (int& x : v) Place[x] = 1;
    int ret = Ask(i,j,Place);
    for (int& x : v) Place[x] = 0;
    return ret;
}

void solveLine() {
    int l = path[0];
    while (true) {
        int it = SZ(path);
        FOR(i,0,SZ(path)-1) if (path[i] == l) { it = i+1; break; }

        int u;
        if (it < SZ(path)) u = path[it];
        else break;

        while (true) {
            //TRACE("CHECK" _ l _ u);
            if (myask(l,u,{})) {
                //TRACE("ANSWER" _ l _ u);
                myans(l,u);
                l = u;
                break;
            }

            int lo = -1, hi = SZ(rem);
            while (hi-lo > 1) {
                int mid = (lo+hi)/2;

                vector<int> v2;
                FOR(i,0,mid) v2.push_back(rem[i]);
                if (myask(l,u,v2)) hi = mid;
                else lo = mid;
            }
            u = rem[hi];

            rem.erase(find(ALL(rem),u));
            FOR(i,0,SZ(path)-1) if (path[i] == l) {
                path.insert(path.begin()+i+1, u);
                break;
            }
        }
    }
    //cerr << "path: "; for (int& x : path) { cerr << x << ' '; } cerr << endl;
    //cerr << "rem: "; for (int& x : rem) { cerr << x << ' '; } cerr << endl;
}

void dfs(int u, int p) {
    preorder.push_back(u);
    pa[u] = -1;
    solved[u] = 1;
    for (int& v : al[u]) if (v != p) {
        dfs(v,u);
    }
}

void Detect(int T, int N) {
    if (T == 1) {
        FOR(i,0,N-1){
            FOR(j,i+1,N-1){
                Place[i] = Place[j] = 1;
                if (Ask(i,j,Place)) Answer(i,j);
                Place[i] = Place[j] = 0;
            }
        }
    } else {
        path.push_back(0);
        path.push_back(N-1);

        FOR(i,1,N-2) rem.push_back(i);

        solveLine();
        while (SZ(rem)) {
            int u = rem.back(); rem.pop_back();

            preorder.clear();
            dfs(0,-1);
            //cerr << "preorder: "; for (int& x : preorder) { cerr << x << ' '; } cerr << endl;

            int lo = -1, hi = SZ(preorder);
            while (hi-lo > 1) {
                int mid = (lo+hi)/2;

                vector<int> v2;
                FOR(i,0,mid) v2.push_back(preorder[i]);
                FOR(i,0,N-1) if (!solved[i]) v2.push_back(i);
                if (myask(0,u,v2)) hi = mid;
                else lo = mid;
            }
            int rt = preorder[hi];
            //TRACE((hi < SZ(preorder)) _ rt _ u);

            path.clear();
            path.push_back(rt);
            path.push_back(u);
            solveLine();
        }
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 8 ms 332 KB Output is correct
3 Correct 5 ms 332 KB Output is correct
4 Correct 6 ms 332 KB Output is correct
5 Correct 6 ms 332 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 556 KB Output is correct
2 Correct 174 ms 532 KB Output is correct
3 Correct 117 ms 528 KB Output is correct
4 Correct 64 ms 552 KB Output is correct
5 Correct 64 ms 548 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 516 KB Output is correct
2 Correct 248 ms 544 KB Output is correct
3 Correct 244 ms 544 KB Output is correct
4 Correct 263 ms 652 KB Output is correct
5 Correct 230 ms 532 KB Output is correct
6 Correct 244 ms 588 KB Output is correct
7 Correct 250 ms 564 KB Output is correct
8 Correct 251 ms 540 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 484 KB Output is correct
2 Correct 259 ms 588 KB Output is correct
3 Correct 218 ms 512 KB Output is correct
4 Correct 156 ms 540 KB Output is correct
5 Correct 223 ms 660 KB Output is correct
6 Correct 162 ms 580 KB Output is correct
7 Correct 154 ms 460 KB Output is correct
8 Correct 206 ms 648 KB Output is correct
9 Correct 175 ms 588 KB Output is correct
10 Correct 175 ms 532 KB Output is correct
11 Correct 222 ms 648 KB Output is correct
12 Correct 229 ms 556 KB Output is correct
13 Correct 119 ms 460 KB Output is correct
14 Correct 224 ms 560 KB Output is correct
15 Correct 122 ms 580 KB Output is correct
16 Correct 247 ms 544 KB Output is correct
17 Correct 65 ms 580 KB Output is correct
18 Correct 208 ms 672 KB Output is correct
19 Correct 106 ms 588 KB Output is correct
20 Correct 180 ms 524 KB Output is correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 214 ms 552 KB Wrong Answer[6]
2 Halted 0 ms 0 KB -