Submission #212819

#	Time	Username	Problem	Language	Result	Execution time	Memory
212819		anonymous	Simurgh (IOI17_simurgh)	C++14	13 / 100	34 ms	7416 KiB

simurgh

#include "simurgh.h"
#include<vector>
#include<queue>
#include<utility>
#include<iostream>
#define MAXN 505
using namespace std;
vector<pair<int,int> > adj[MAXN], Tree[MAXN]; //to, edge id
vector<int> TreeId, Ans;
int N,M,X, rt = 0; //spanning tree count
int low[MAXN], lowid[MAXN], par[MAXN], parid[MAXN], depth[MAXN], res[MAXN];
bool golden[MAXN], vis[MAXN], vis2[MAXN], done[MAXN];

//tree making phrase
void dfs(int u) { //make dfs tree
    vis[u] = true;
    for (auto v: adj[u]) {
        if (!vis[v.first]) {
            TreeId.push_back(v.second);
            Tree[u].push_back(v);
            Tree[v.first].push_back({u,v.second});
            depth[v.first] = depth[u] + 1;
            par[v.first] = u, parid[v.first] = v.second;
            dfs(v.first);
        }
    }
}

void solveTree(int u) { //solve dfs tree's identity
    vis2[u] = true, low[u] = u;
    int chd_low = u;
    for (auto v: adj[u]) {
        if (vis2[v.first] && v.first != par[u]) {
            if (depth[low[u]] > depth[v.first]) {
                low[u] = v.first;
                lowid[u] = v.second;
            }
        } else if (!vis2[v.first]) {
            solveTree(v.first);
            if (depth[chd_low] > depth[low[v.first]]) {
                chd_low = low[v.first];
            }
        }
    }
    if (low[u] == u && chd_low == u && u != rt) {
        golden[parid[u]] = true;
        done[parid[u]] = true; //which edges u-par(u) have been solved?
    } else if (depth[low[u]] >= depth[chd_low]) {
        low[u] = chd_low; //relax
    } else {
        int cur = u, seen_normal = false, t1=false, t2=false, t3=false;
        while (cur != low[u] && cur != rt) {
            if (!done[parid[cur]] || (!seen_normal && !golden[parid[cur]])) {
                //printf("Solving %d. Par=%d. Edge Id %d, low = %d non-tree=%d\n", cur, par[cur], parid[cur], low[u],lowid[u]);
                vector<int> query;
                query.push_back(lowid[u]);
                for (int i=0; i<N-1; i++) {
                    if (TreeId[i] != parid[cur]) {
                        query.push_back(TreeId[i]);
                    }
                }
                res[cur] = count_common_roads(query);
                if (res[cur] == X-1) {
                    t1 = true;
                } else if (res[cur] == X) {
                    t2 = true;
                } else if (res[cur] == X+1) {
                    t3 = true;
                }
                if (done[parid[cur]]) {seen_normal = true;}
            }
            cur = par[cur];
        }
        cur = u;
        while (cur != low[u] && cur != rt) {
            if (!done[parid[cur]]) {
                done[parid[cur]] = true;
                if (t1 && res[cur] == X-1) {
                    golden[parid[cur]] = true;
                } else if (t3 && res[cur] == X) {
                    golden[parid[cur]] = true;
                }
            }
            cur = par[cur];
        }
        done[lowid[u]] = true;
        if (t3 == true) {
            golden[lowid[u]] = true;
        }
    }
}

//Solving phrase
int Num(vector<pair<int,int> > Eset, int v) {
    int C = Eset.size(), D = 0; //count golden in Eset, adj of v
    bool vis3[MAXN] = {};
    queue<int> Q;
    vector<int> Query;
    for (auto e: Eset) {
        Tree[v].push_back(e);
    }
    Q.push(v), vis3[v] = true;
    while (Q.size()) {
        int cur = Q.front();
        Q.pop();
        for (int i=Tree[cur].size()-1; i>=0; i--) {
            if (!vis3[Tree[cur][i].first]) {
                vis3[Tree[cur][i].first] = true;
                Q.push(Tree[cur][i].first);
                Query.push_back(Tree[cur][i].second);
                if (done[Tree[cur][i].second]) {
                    D += (int) golden[Tree[cur][i].second];
                }
            }
        }
    }
    for (int i=0; i<C; i++) {
        Tree[v].pop_back();
    }
    return(count_common_roads(Query) - D);
}

void FindGolden(int u) {
    vector <pair<int,int> > todo;
    for (auto v: adj[u]) {
        if (!done[v.second]) {
            todo.push_back(v); //all not done
        }
    }
    int deg = Num(todo, u);
    for (int i=0; i<deg; i++) {
        vector <pair<int,int> > Maybe;
        for (auto v: adj[u]) {
            if (!done[v.second]) {
                Maybe.push_back(v);
            }
        }
        int lo = 0, hi = Maybe.size()-1;
        while (lo != hi) {
            int mid = (lo + hi) >> 1;
            vector<pair<int,int> > query;
            for (int j=lo; j<=mid; j++) {
                query.push_back(Maybe[j]);
            }
            if (Num(query, u)) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
        golden[Maybe[hi].second] = true;
        done[Maybe[hi].second] = true;
    }
    for (auto v: adj[u]) {
        done[v.second] = true;
    }
}

vector<int> find_roads(int n, vector<int> u, vector<int> v) {
	N = n, M = u.size();
	for (int i=0; i<M; i++) {
        adj[u[i]].push_back({v[i],i});
        adj[v[i]].push_back({u[i],i});
	}
	par[rt] = -1, dfs(rt);
	X = count_common_roads(TreeId);
	solveTree(rt);
	for (int i=0; i<N; i++) {
        FindGolden(i); //find all golden edges adj to i
	}
	for (int i=0; i<M; i++) {
        if (golden[i]) {
            Ans.push_back(i);
        }
	}
	return(Ans);
}

Compilation message (stderr)

simurgh.cpp: In function 'void solveTree(int)':
simurgh.cpp:51:53: warning: variable 't2' set but not used [-Wunused-but-set-variable]
         int cur = u, seen_normal = false, t1=false, t2=false, t3=false;
                                                     ^~

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