Submission #1290590

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290590		mariaclara	Simurgh (IOI17_simurgh)	C++17	51 / 100	100 ms	2328 KiB

simurgh

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

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mk make_pair
#define pb push_back
#define fr first
#define sc second

int n;
vi pai;
vector<vector<pii>> tree;

void reset_dsu() {
    pai.resize(n);
    for(int i = 0; i < n; i++) pai[i] = i;
}

int find(int x) {
    if(x == pai[x]) return x;
    return pai[x] = find(pai[x]);
}

void join(int x, int y) {
    pai[find(x)] = pai[find(y)];
}

vi cam, visited;

bool dfs(int x, int y) {
    visited[x] = 1;
    if(x == y) return 1;

    for(auto [viz, id] : tree[x]) {
        if(visited[viz]) continue;

        cam.pb(id);
        if(dfs(viz, y)) return 1;
        cam.pop_back();
    }

    return 0;
}

void call_dfs(int x, int y) {
    cam.clear();
    visited.clear();
    visited.resize(n);
    dfs(x, y);
}

vi find_roads(int N, vi u, vi v) {
    n = N;
    int m = sz(u);
    tree.resize(n);

    reset_dsu();

    vi tree_set, state(m, -1), pos(m, -1);

    for(int i = 0; i < m; i++) {
        if(find(u[i]) == find(v[i])) continue;

        tree[u[i]].pb({v[i], i});
        tree[v[i]].pb({u[i], i});

        join(u[i], v[i]);

        pos[i] = sz(tree_set);
        tree_set.pb(i);
    }

    int tree_qtd = count_common_roads(tree_set);

    for(int i = 0; i < m; i++) {
        if(pos[i] != -1) continue;

        call_dfs(u[i], v[i]);
        vi rsp;
        int k = -1, max_rsp = tree_qtd;

        for(int j : cam) {
            if(state[j] != -1) {
                rsp.pb(-1);
                k = j;
                continue;
            }

            tree_set[pos[j]] = i;
            int new_qtd = count_common_roads(tree_set);
            rsp.pb(new_qtd);

            tree_set[pos[j]] = j;
            max_rsp = max(max_rsp, new_qtd);
        }

        if(k != -1) { // por causa dessa parte fica Q ~ n(n-1)/2 
            tree_set[pos[k]] = i;
            int new_qtd = count_common_roads(tree_set);
            tree_set[pos[k]] = k;
            max_rsp = new_qtd + state[k];
        }

        for(int j = 0; j < sz(cam); j++)
            if(state[cam[j]] == -1) state[cam[j]] = rsp[j] != max_rsp;

        state[i] = tree_qtd != max_rsp; 
    }

    vi ans;

    for(int i = 0; i < m; i++)
        if(state[i]) ans.pb(i);
    
    return ans;
}

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