Submission #466859

#	Time	Username	Problem	Language	Result	Execution time	Memory
466859		idk321	Triangles (CEOI18_tri)	C++17	35 / 100	118 ms	320 KiB

tri

#include <bits/stdc++.h>
#include "trilib.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;
}

bool isGood(int node) {
    for (int i = 0; i < N; i++) {
        vis[i] = false;
        adj[i].clear();
    }
    for (int i = 1; i <= n; i++) {
        if (i == node) continue;
        int f1 = 0;
        int f2 = 0;
        for (int j = 1; j <= n; j++) {
            if (j == node || j == i) continue;
            if (is_clockwise(node, i, j)) {
                f1++;
            } else f2++;
        }
        if (!f1 || !f2) return true;
    }
    return false;
}

int getRes(int node) {
    int first = -1;
    for (int i = 1; i <= n; i++) {
        if (i == node) continue;
        bool good = true;
        for (int j = i + 1; j <= n; j++) {
            if (i == node || j == node) continue;
            if (!is_clockwise(node, i, j)) {
                good = false;
                break;
            }
        }
        if (good) {
            first = i;
            break;
        }
    }

    int cur = first;
    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: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 20 / 20
• Subtask 5: 0 / 25