oj.uz

Submission #1067586

# Submission time Handle Problem Language Result Execution time Memory
1067586 2024-08-20T20:47:25 Z Unforgettablepl Park (JOI17_park) C++17
77 / 100
 267 ms 852 KB 
#include "park.h"
#include <bits/stdc++.h>
using namespace std;

static int Place[1400];

void strat1(int N) {
    for(int i=0;i<N;i++) {
        for(int j=i+1;j<N;j++) {
            Place[i]=Place[j]=1;
            if(Ask(i,j,Place))Answer(i,j);
            Place[i]=Place[j]=0;
        }
    }
}

void stratTree(int N) {
    vector<bool> used(N);
    vector<vector<int>> adj(N);
    used[0]=true;
    for(int y=1;y<N;y++) {
        if(used[y])continue;
        stack<int> s;
        s.emplace(y);
        vector<int> arm;
        while(!s.empty()) {
            int curr = s.top();s.pop();
            used[curr]=true;
            function check = [&](int x) {
                for(int i=0;i<x;i++)Place[i]=true;
                for(int i=0;i<N;i++)if(used[i])Place[i]=true;
                bool ans = Ask(0,curr,Place);
                for(int i=0;i<N;i++)Place[i]=false;
                return !ans;
            };
            int ans = -1;
            for(int jump=1024;jump;jump/=2) {
                if(ans+jump>=N)continue;
                if(check(ans+jump))ans+=jump;
            }
            if(ans==-1)arm.emplace_back(curr);
            else {
                s.emplace(curr);
                s.emplace(ans);
            }
        }
        for(int i=1;i<arm.size();i++) {
            adj[arm[i]].emplace_back(arm[i-1]);
            adj[arm[i-1]].emplace_back(arm[i]);
            Answer(min(arm[i],arm[i-1]),max(arm[i],arm[i-1]));
        }
        vector<int> order;
        function<void(int,int)> dfs = [&](int x,int p) {
            order.emplace_back(x);
            for(int&i:adj[x])if(i!=p)dfs(i,x);
        };
        dfs(0,-1);
        function check = [&](int x) {
            for(int i=0;i<x;i++)Place[order[i]]=true;
            Place[arm[0]]=true;
            bool ans = Ask(0,arm[0],Place);
            for(int i=0;i<N;i++)Place[i]=false;
            return !ans;
        };
        int ans = 0;
        for(int jump=1024;jump;jump/=2) {
            if(ans+jump>=order.size())continue;
            if(check(ans+jump))ans+=jump;
        }
        adj[order[ans]].emplace_back(arm[0]);
        adj[arm[0]].emplace_back(order[ans]);
        Answer(min(arm[0],order[ans]),max(arm[0],order[ans]));
    }
}

void Detect(int T, int N) {
    if(T==1)strat1(N);
    else stratTree(N);
}

Compilation message

park.cpp: In function 'void stratTree(int)':
park.cpp:47:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |         for(int i=1;i<arm.size();i++) {
      |                     ~^~~~~~~~~~~
park.cpp:67:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |             if(ans+jump>=order.size())continue;
      |                ~~~~~~~~^~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 3 ms 348 KB Output is correct
3 Correct 4 ms 348 KB Output is correct
4 Correct 4 ms 348 KB Output is correct
5 Correct 4 ms 344 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 616 KB Output is correct
2 Correct 132 ms 848 KB Output is correct
3 Correct 148 ms 612 KB Output is correct
4 Correct 240 ms 616 KB Output is correct
5 Correct 234 ms 848 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 592 KB Output is correct
2 Correct 174 ms 596 KB Output is correct
3 Correct 180 ms 596 KB Output is correct
4 Correct 163 ms 596 KB Output is correct
5 Correct 192 ms 592 KB Output is correct
6 Correct 174 ms 592 KB Output is correct
7 Correct 168 ms 552 KB Output is correct
8 Correct 172 ms 348 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 348 KB Output is correct
2 Correct 196 ms 600 KB Output is correct
3 Correct 186 ms 556 KB Output is correct
4 Correct 219 ms 592 KB Output is correct
5 Correct 237 ms 828 KB Output is correct
6 Correct 223 ms 592 KB Output is correct
7 Correct 218 ms 596 KB Output is correct
8 Correct 214 ms 564 KB Output is correct
9 Correct 208 ms 596 KB Output is correct
10 Correct 220 ms 824 KB Output is correct
11 Correct 222 ms 564 KB Output is correct
12 Correct 196 ms 572 KB Output is correct
13 Correct 241 ms 580 KB Output is correct
14 Correct 216 ms 600 KB Output is correct
15 Correct 267 ms 592 KB Output is correct
16 Correct 180 ms 348 KB Output is correct
17 Correct 234 ms 604 KB Output is correct
18 Correct 209 ms 852 KB Output is correct
19 Correct 229 ms 572 KB Output is correct
20 Correct 212 ms 796 KB Output is correct

Subtask #5
0 / 23.0

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