Submission #466870

#	Time	Username	Problem	Language	Result	Execution time	Memory
466870		idk321	Triangles (CEOI18_tri)	C++17	55 / 100	143 ms	972 KiB

tri

#include "trilib.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 501;
vector<int> adj[N];
bool vis[N];
bool st[N];
int n;
bool cycle(int node) {
    if (st[node]) return true;
    if (vis[node]) return false;
    vis[node] = true;
    st[node] = true;
    for (int next : adj[node]) {
        if (cycle(next)) return true;
    }
    st[node] = false;
    return false;
}

int cur = -1;

bool isGood(int node) {
    for (int i = 0; i < N; i++) {
        st[i] = false;
        vis[i] = false;
        adj[i].clear();
    }
    vector<int> nodes;
    for (int i = 1; i <= n; i++) if (i != node) nodes.push_back(i);
    int biggest = nodes[0];
    for (int i = 0; i < n - 2; i++) {
        if (is_clockwise(node, nodes[i + 1], biggest)) biggest = nodes[i + 1];
    }

    for (int i = 0; i < n - 2; i++) {
        if (nodes[i] == biggest) continue;
        if (is_clockwise(node, nodes[i], biggest)) {
            return false;
        }
    }

    cur = biggest;
    return true;
}

int getRes(int node) {
    int prev = node;
    int res = 1;
    while (cur != node) {
        int next = -1;
        for (int i = 1; i <= n; i++) {
            if (i == prev) continue;
            if (i == cur) continue;
            if (next == -1) next = i;
            else {
                if (is_clockwise(cur, i, next)) {
                    next = i;
                }
            }
        }
        prev = cur;
        cur = next;
        res++;
    }
    return res;
}

int main() {
    n = get_n();

    for (int i = 1; i <= n; i++) {
        if (isGood(i)) {
            int res = getRes(i);
            give_answer(res);
            break;
        }
    }
}

/*
6
1 1
4 3
2 2
1 4
5 1
3 2
*/

• Subtask 1: 15 / 15
• Subtask 2: 20 / 20
• Subtask 3: 0 / 20
• Subtask 4: 20 / 20
• Subtask 5: 0 / 25