Submission #59187

#	Time	Username	Problem	Language	Result	Execution time	Memory
59187		duality	Simurgh (IOI17_simurgh)	C++11	100 / 100	210 ms	11256 KiB

simurgh

#define DEBUG 0

#include <bits/stdc++.h>
using namespace std;

#if DEBUG
// basic debugging macros
int __i__,__j__;
#define printLine(l) for(__i__=0;__i__<l;__i__++){cout<<"-";}cout<<endl
#define printLine2(l,c) for(__i__=0;__i__<l;__i__++){cout<<c;}cout<<endl
#define printVar(n) cout<<#n<<": "<<n<<endl
#define printArr(a,l) cout<<#a<<": ";for(__i__=0;__i__<l;__i__++){cout<<a[__i__]<<" ";}cout<<endl
#define print2dArr(a,r,c) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<a[__i__][__j__]<<" ";}cout<<endl;}
#define print2dArr2(a,r,c,l) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<setw(l)<<setfill(' ')<<a[__i__][__j__]<<" ";}cout<<endl;}

// advanced debugging class
// debug 1,2,'A',"test";
class _Debug {
    public:
        template<typename T>
        _Debug& operator,(T val) {
            cout << val << endl;
            return *this;
        }
};
#define debug _Debug(),
#else
#define printLine(l)
#define printLine2(l,c)
#define printVar(n)
#define printArr(a,l)
#define print2dArr(a,r,c)
#define print2dArr2(a,r,c,l)
#define debug
#endif

// define
#define MAX_VAL 999999999
#define MAX_VAL_2 999999999999999999LL
#define EPS 1e-6
#define mp make_pair
#define pb push_back

// typedef
typedef unsigned int UI;
typedef long long int LLI;
typedef unsigned long long int ULLI;
typedef unsigned short int US;
typedef pair<int,int> pii;
typedef pair<LLI,LLI> plli;
typedef vector<int> vi;
typedef vector<LLI> vlli;
typedef vector<pii> vpii;
typedef vector<plli> vplli;

// ---------- END OF TEMPLATE ----------
#include "simurgh.h"

int label[500][500],know[500][500];
vi adjList[500];
int parent[500],disc[500],low[500],lowlabel[500];
int com[500],first[500];
int num = 0,bcc = 0;
vi S,tree;
int doDFS(int u,int p) {
    int i;
    parent[u] = p,disc[u] = low[u] = num++;
    S.pb(u);
    for (i = 0; i < adjList[u].size(); i++) {
        int v = adjList[u][i];
        if (disc[v] == -1) {
            tree.pb(label[u][v]),doDFS(v,u);
            if (low[v] < low[u]) low[u] = low[v],lowlabel[u] = lowlabel[v];
            if (low[v] > disc[u]) {
                while (1) {
                    int w = S.back();
                    S.pop_back();
                    com[w] = bcc;
                    if (w == v) break;
                }
                bcc++;
            }
        }
        else if ((v != p) && (disc[v] < low[u])) low[u] = disc[v],lowlabel[u] = label[u][v];
    }
    return 0;
}
int s[500],r[500];
vpii adjList2[125000];
int royal[125000];
int doDFS2(int u,int rr) {
    if (royal[u] != -1) return 0;
    int i;
    royal[u] = rr;
    for (i = 0; i < adjList2[u].size(); i++) doDFS2(adjList2[u][i].first,rr+adjList2[u][i].second);
    return 0;
}
int ds[500];
int find(int n) {
    if (ds[n] != n) ds[n] = find(ds[n]);
    return ds[n];
}
int query(vi forest,vi &u,vi &v,int n) {
    int i;
    for (i = 0; i < n; i++) ds[i] = i;
    for (i = 0; i < forest.size(); i++) ds[find(u[forest[i]])] = find(v[forest[i]]);
    int sub = 0;
    for (i = 0; i < tree.size(); i++) {
        int pu = find(u[tree[i]]),pv = find(v[tree[i]]);
        if (pu != pv) forest.pb(tree[i]),sub += royal[tree[i]],ds[pu] = pv;
    }
    return count_common_roads(forest)-sub;
}
int findAll(vi &poss,vi &u,vi &v,int n,int l,int r,int s) {
    if (s == 0) {
        int i;
        for (i = l; i <= r; i++) royal[poss[i]] = 0;
        return 0;
    }
    if (l == r) {
        royal[poss[l]] = 1;
        return 0;
    }

    int i,m = (l+r) / 2;
    vi ask;
    for (i = l; i <= m; i++) ask.pb(poss[i]);
    int ls = query(ask,u,v,n);
    findAll(poss,u,v,n,l,m,ls);
    findAll(poss,u,v,n,m+1,r,s-ls);
    return 0;
}
vector<int> find_roads(int n,vector<int> u,vector<int> v) {
    int i,j;
    memset(label,-1,sizeof(label));
    memset(royal,-1,sizeof(royal));
    for (i = 0; i < u.size(); i++) {
        label[u[i]][v[i]] = label[v[i]][u[i]] = i;
        adjList[u[i]].pb(v[i]);
        adjList[v[i]].pb(u[i]);
    }
    for (i = 0; i < n; i++) disc[i] = low[i] = -1;
    doDFS(0,-1);
    while (!S.empty()) {
        int w = S.back();
        S.pop_back();
        com[w] = bcc;
    }
    bcc++;
    int t = count_common_roads(tree);
    for (i = 0; i < bcc; i++) s[i] = r[i] = -1;
    for (i = 1; i < n; i++) {
        int u = label[i][parent[i]],v = lowlabel[i];
        if (com[i] == com[parent[i]]) {
            int p = find(tree.begin(),tree.end(),u)-tree.begin();
            tree[p] = v;
            int t2 = count_common_roads(tree);
            tree[p] = u;
            adjList2[u].pb(mp(v,t2-t));
            adjList2[v].pb(mp(u,t-t2));
            if (t != t2) s[com[i]] = u,r[com[i]] = (t > t2);
            int w = i;
            while (disc[parent[w]] != low[i]) w = parent[w];
            w = label[w][parent[w]];
            p = find(tree.begin(),tree.end(),w)-tree.begin();
            tree[p] = v;
            t2 = count_common_roads(tree);
            tree[p] = w;
            adjList2[w].pb(mp(v,t2-t));
            adjList2[v].pb(mp(w,t-t2));
            if (t != t2) s[com[i]] = w,r[com[i]] = (t > t2);
            first[com[i]] = u;
        }
        else royal[u] = 1;
    }
    for (i = 0; i < bcc; i++) {
        if (s[i] == -1) s[i] = first[i],r[i] = 0;
        doDFS2(s[i],r[i]);
    }
    for (i = 0; i < n; i++) {
        vi poss;
        for (j = 0; j < adjList[i].size(); j++) {
            int v = adjList[i][j];
            if ((v > i) && (royal[label[i][v]] == -1)) poss.pb(label[i][v]);
        }
        findAll(poss,u,v,n,0,poss.size()-1,query(poss,u,v,n));
    }
    vi ans;
    for (i = 0; i < u.size(); i++) {
        if (royal[i]) ans.pb(i);
    }
    return ans;
}

Compilation message (stderr)

simurgh.cpp: In function 'int doDFS(int, int)':
simurgh.cpp:69:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < adjList[u].size(); i++) {
                 ~~^~~~~~~~~~~~~~~~~~~
simurgh.cpp: In function 'int doDFS2(int, int)':
simurgh.cpp:95:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < adjList2[u].size(); i++) doDFS2(adjList2[u][i].first,rr+adjList2[u][i].second);
                 ~~^~~~~~~~~~~~~~~~~~~~
simurgh.cpp: In function 'int query(vi, vi&, vi&, int)':
simurgh.cpp:106:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < forest.size(); i++) ds[find(u[forest[i]])] = find(v[forest[i]]);
                 ~~^~~~~~~~~~~~~~~
simurgh.cpp:108:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < tree.size(); i++) {
                 ~~^~~~~~~~~~~~~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:137:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < u.size(); i++) {
                 ~~^~~~~~~~~~
simurgh.cpp:182:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (j = 0; j < adjList[i].size(); j++) {
                     ~~^~~~~~~~~~~~~~~~~~~
simurgh.cpp:189:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < u.size(); i++) {
                 ~~^~~~~~~~~~

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