Submission #597904

#	Time	Username	Problem	Language	Result	Execution time	Memory
597904		yanndev	Simurgh (IOI17_simurgh)	C++17	13 / 100	30 ms	6984 KiB

simurgh

#include <bits/stdc++.h>
#include "simurgh.h"
#define fi first
#define se second
using namespace std;

const int IDK = 0;
const int NOT_ROYAL = 1;
const int ROYAL = 2;

vector<pair<int, int>> graph[542];
vector<int> back[542];
bool vis[542];
bool dfsTree[4242];
int status[4242];

void dfs(int node, int root, int subId = -1) {
    vis[node] = true;
    for (auto& x: graph[node]) {
        if (vis[x.fi] && x.fi == root)
            back[subId].push_back(x.se);
        if (!vis[x.fi]) {
            int nxtId = subId;
            if (subId == -1)
                nxtId = x.fi;
            dfsTree[x.se] = true;
            dfs(x.fi, root, nxtId);
        }
    }
}

vector<int> find_roads(int n, vector<int> u, vector<int> v) {
    int m = (int)u.size();
    for (int i = 0; i < m; i++) {
        graph[u[i]].push_back({v[i], i});
        graph[v[i]].push_back({u[i], i});
    }

    //printf("n is %d\n", n);

    for (int i = 0; i < n; i++) {
        //printf("node %d\n", i);
        
        for (int id = 0; id < (int)graph[i].size(); id++) {
            auto& x = graph[i][0];
            // x.se a royal edge ???
            /*if (status[x.se] != IDK) {
                rotate(graph[i].begin(), graph[i].begin() + 1, graph[i].end());
                continue;
            }*/

            memset(vis, false, sizeof(vis));
            memset(dfsTree, false, sizeof(dfsTree));
            for (int j = 0; j < n; j++)
                back[j].clear();
            dfs(i, i, -1);

            //printf("is %d\n", x.se);

            vector<int> toQ {};
            for (int j = 0; j < m; j++) {
                if (dfsTree[j] && j != x.se) {
                    toQ.push_back(j);
                    //printf("%d ", j);
                }
            }
            //printf("%d\n", x.se);
            toQ.push_back(x.se);
            int orig = count_common_roads(toQ);
            //printf("cnt %d\n", orig);
            status[x.se] = ROYAL;

            for (auto& y: back[x.fi]) {
                if (y == x.se)
                    continue;
                toQ.pop_back();
                toQ.push_back(y);
                //printf("back %d\n", y);
                int newCnt = count_common_roads(toQ);
                //printf("new cnt %d\n", newCnt);
                /*if (newCnt == orig)
                    status[x.se] = NOT_ROYAL;*/
                /*if (newCnt < orig) {
                    status[x.se] = ROYAL;
                    status[y] = NOT_ROYAL;
                }*/

                if (newCnt > orig) {
                    status[x.se] = NOT_ROYAL;
                    status[y] = ROYAL;
                }
            }

            rotate(graph[i].begin(), graph[i].begin() + 1, graph[i].end());
        }
        //printf("endnode %d\n", i);
    }

    vector<int> ans {};
    for (int i = 0; i < m; i++)
        if (status[i] == ROYAL)
            ans.push_back(i);

    /*printf("ans ");
    for (auto& x: ans)
        printf("%d ", x);
    printf("\n");*/
    return ans;
}

• Subtask 1: 13 / 13
• Subtask 2: 0 / 17
• Subtask 3: 0 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 30