Submission #301519

#	Time	Username	Problem	Language	Result	Execution time	Memory
301519		qpwoeirut	Comparing Plants (IOI20_plants)	C++17	0 / 100	4054 ms	96632 KiB

plants

#include "plants.h"
#include <bits/stdc++.h>

using namespace std;

int N;
vector<set<int>> adj;
void init(int k, vector<int> r) {
    N = r.size();
    adj = vector<set<int>>(N, set<int>());
    for (int i=0; i<N; ++i) {
        int u = i, v = (i+1) % N;
        if (r[u] == 0) {
            adj[u].insert(v);
        } else {
            adj[v].insert(u);
        }
    }
}

int compare_plants(int x, int y) {
    vector<bool> visited(N);
    queue<int> q;
    q.push(x);
    visited[x] = true;
    while (q.size() > 0) {
        int cur = q.front(); q.pop();
        for (auto it=adj[cur].begin(); it!=adj[cur].end(); ++it) {
            if (!visited[*it]) {
                adj[x].insert(*it);
                if (*it == y) {
                    return 1;
                }
                visited[*it] = true;
                q.push(*it);
            }
        }
    }
    fill(visited.begin(), visited.end(), false);
    q.push(y);
    visited[y] = true;
    while (q.size() > 0) {
        int cur = q.front(); q.pop();
        for (auto it=adj[cur].begin(); it!=adj[cur].end(); ++it) {
            if (!visited[*it]) {
                adj[y].insert(*it);
                if (*it == x) {
                    return -1;
                }
                visited[*it] = true;
                q.push(*it);
            }
        }
    }

    return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 14
• Subtask 3: 0 / 13
• Subtask 4: 0 / 17
• Subtask 5: 0 / 11
• Subtask 6: 0 / 15
• Subtask 7: 0 / 25