oj.uz

Submission #1067585

# Submission time Handle Problem Language Result Execution time Memory
1067585 2024-08-20T20:47:13 Z Unforgettablepl Park (JOI17_park) C++17
77 / 100
 261 ms 848 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 4 ms 464 KB Output is correct
3 Correct 3 ms 348 KB Output is correct
4 Correct 4 ms 344 KB Output is correct
5 Correct 4 ms 348 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 245 ms 612 KB Output is correct
2 Correct 127 ms 600 KB Output is correct
3 Correct 147 ms 604 KB Output is correct
4 Correct 235 ms 848 KB Output is correct
5 Correct 227 ms 612 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 568 KB Output is correct
2 Correct 171 ms 812 KB Output is correct
3 Correct 174 ms 596 KB Output is correct
4 Correct 164 ms 560 KB Output is correct
5 Correct 180 ms 596 KB Output is correct
6 Correct 171 ms 564 KB Output is correct
7 Correct 171 ms 592 KB Output is correct
8 Correct 174 ms 564 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 229 ms 544 KB Output is correct
3 Correct 187 ms 592 KB Output is correct
4 Correct 215 ms 592 KB Output is correct
5 Correct 219 ms 600 KB Output is correct
6 Correct 261 ms 596 KB Output is correct
7 Correct 221 ms 592 KB Output is correct
8 Correct 206 ms 592 KB Output is correct
9 Correct 211 ms 592 KB Output is correct
10 Correct 223 ms 848 KB Output is correct
11 Correct 218 ms 564 KB Output is correct
12 Correct 205 ms 592 KB Output is correct
13 Correct 229 ms 592 KB Output is correct
14 Correct 227 ms 592 KB Output is correct
15 Correct 241 ms 560 KB Output is correct
16 Correct 170 ms 596 KB Output is correct
17 Correct 248 ms 604 KB Output is correct
18 Correct 216 ms 596 KB Output is correct
19 Correct 227 ms 596 KB Output is correct
20 Correct 251 ms 556 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 -