oj.uz

Submission #597873

# Submission time Handle Problem Language Result Execution time Memory
597873 2022-07-17T03:11:40 Z yanndev Simurgh (IOI17_simurgh) C++17
0 / 100
 595 ms 1048576 KB 
#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);
        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});
    }

    for (int i = 0; i < n; i++) {
        memset(vis, false, sizeof(vis));
        memset(dfsTree, false, sizeof(vis));
        for (int j = 0; j < n; j++)
            back[j].clear();
        
        dfs(i, i, -1);
        for (auto& x: graph[i]) {
            // x.se a royal edge ???
            if (status[x.se] != IDK)
                continue;

            vector<int> toQ {};
            for (int j = 0; j < m; j++)
                if (dfsTree[j] && j != x.se)
                    toQ.push_back(j);
            toQ.push_back(x.se);
            int orig = count_common_roads(toQ);
            status[x.se] = ROYAL;

            for (auto& y: back[x.fi]) {
                toQ.pop_back();
                toQ.push_back(y);
                int newCnt = count_common_roads(toQ);
                if (newCnt > orig) {
                    status[x.se] = NOT_ROYAL;
                    status[y] = ROYAL;
                }
            }
        }
    }

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

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 595 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 595 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 595 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Runtime error 531 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 595 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -