oj.uz

Submission #904836

# Submission time Handle Problem Language Result Execution time Memory
904836 2024-01-12T10:12:32 Z 406 Meetings (JOI19_meetings) C++17
0 / 100
 40 ms 668 KB 
#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;

void bridge(int u, int v) {
        if (u > v) swap(u, v);
        Bridge(u, v);
}

void solve(vector<int> &T) {
        if (T.size() <= 1) 
                return;
        if (T.size() == 2) {
                bridge(T[0], T[1]);
                return;
        }
        vector<int> path;
        map<int, vector<int>> S;

        for (int i = 2; i < T.size(); ++i) {
                int q = Query(T[0], T[1], T[i]);
                if (q != T[0] || q != T[1]) path.push_back(q);
                S[q].push_back(T[i]);
        }
        sort(path.begin(), path.end());
        path.resize(unique(path.begin(), path.end()) - path.begin());

        S[T[0]].push_back(T[0]);
        S[T[1]].push_back(T[1]);
        for (auto [u, T0]: S) solve(T0);

        sort(path.begin(), path.end(), [&](int u, int v) {return Query(T[0], u, v) == u;});
        path.insert(path.begin(), T[0]);
        path.push_back(T[1]);
        for (int i = 1; i < path.size(); ++i) {
                bridge(path[i], path[i - 1]);
        }
}

void Solve(int32_t n){
        srand(time(NULL));
        vector<int> nodes(n);
        iota(nodes.begin(), nodes.end(), 0);
        mt19937 rng((int64_t) new char);
        shuffle(nodes.begin(), nodes.end(), rng);

        solve(nodes);
}

Compilation message

meetings.cpp: In function 'void solve(std::vector<int>&)':
meetings.cpp:20:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |         for (int i = 2; i < T.size(); ++i) {
      |                         ~~^~~~~~~~~~
meetings.cpp:35:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |         for (int i = 1; i < path.size(); ++i) {
      |                         ~~^~~~~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Incorrect 1 ms 344 KB Wrong Answer [3]
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Incorrect 1 ms 344 KB Wrong Answer [3]
3 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Incorrect 1 ms 344 KB Wrong Answer [3]
3 Halted 0 ms 0 KB -

Subtask #4
0 / 71.0

# Verdict Execution time Memory Grader output
1 Incorrect 40 ms 668 KB Wrong Answer [1]
2 Halted 0 ms 0 KB -