Submission #796954

#	Time	Username	Problem	Language	Result	Execution time	Memory
796954		Magikarp4000	Simurgh (IOI17_simurgh)	C++17	51 / 100	126 ms	9712 KiB

simurgh

#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
#define OPTM ios_base::sync_with_stdio(0); cin.tie(0);
#define INF int(1e9+7)
#define ln '\n' 
#define ll long long
#define ull unsigned long long
#define ui unsigned int
#define us unsigned short
#define FOR(i,s,n) for (int i = s; i < n; i++)
#define FORR(i,n,s) for (int i = n; i > s; i--)
#define FORX(u, arr) for (auto u : arr)
#define PB push_back
#define in(v,x) (v.find(x) != v.end())
#define F first
#define S second
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define UM unordered_map
#define US unordered_set
#define PQ priority_queue
#define ALL(v) v.begin(), v.end()
const ll LLINF = 1e18+1;

const int MAXN = 1e5+5;
int n,m;
int p[MAXN], sz[MAXN];
vector<int> e, comp[MAXN];
vector<PII> v[MAXN], edges;
bool z[MAXN], ze[MAXN], res[MAXN], done[MAXN]; // ze = visited edge, done = processed edge
vector<int> toclr;

int finds(int x) {
    if (p[x] != x) p[x] = finds(p[x]);
    return p[x];
}

void unite(int a, int b, int idx) {
    a = finds(a);
    b = finds(b);
    if (a != b) {
        if (sz[a] < sz[b]) swap(a,b);
        p[b] = a;
        sz[a] += sz[b];
        e.PB(idx);
    }
}

void reset() {
    FOR(i,0,n) z[i] = 0, p[i] = i, sz[i] = 1;
    FORX(u,toclr) ze[u] = 0;
    toclr.clear();
    e.clear();
    FOR(i,0,n) comp[i].clear();
}

void dfs(int s, int num, int src) {
    if (z[s]) return;
    z[s] = 1;
    FORX(u,v[s]) {
        if (u.F == src) {
            ze[u.S] = 1;
            toclr.PB(u.S);
            comp[num].PB(u.S);
        }
        else dfs(u.F,num,src);
    }
}

void print(int s) {
    cout << "s: " << s << "| e: ";
    FORX(y,e) cout << y << " ";
    cout << ln;
}

void solve(int s) {
    reset(); // common w reset
    int cnt = 0;
    // FOR(i,0,m) cout << ze[i] << " ";
    // cout << ln;
    FORX(u,v[s]) {
        if (ze[u.S]) continue;
        ze[u.S] = 1;
        toclr.PB(u.S);
        dfs(u.F,cnt++,s);
    }
    FOR(j,0,m) {
        if (edges[j].F != s && edges[j].S != s) unite(edges[j].F,edges[j].S,j);
    }
    // cout << "s: " << s << ln;
    // FOR(i,0,cnt) {
    //     cout << i << ": ";
    //     FORX(u,comp[i]) cout << u << " ";
    //     cout << ln;
    // }
    FOR(i,0,cnt) {
        // if (comp[i].empty()) continue;
        FOR(j,0,cnt) if (j != i) e.PB(comp[j][0]);
        vector<int> le,gr;
        int orig = -INF, start = 1, isgold = -1;
        FORX(u,comp[i]) {
            if (done[u]) {
                e.PB(u);
                // print(s);
                orig = count_common_roads(e);
                e.pop_back();
                isgold = res[u];
                start = 0;
                break;
            }
        }
        if (isgold == -1) {
            e.PB(comp[i][0]); le.PB(comp[i][0]);
            // print(s);
            orig = count_common_roads(e);
            e.pop_back();
        }
        // int start = 0, cn = comp[i].size();
        // while (start < cn && done[comp[i][start]]) start++;
        // start = max(0,start-1);
        // if (start >= cn) continue;
        // e.PB(comp[i][start]); le.PB(comp[i][start]);
        // cout << "s: " << s << "| e: ";
        // FORX(y,e) cout << y << " ";
        // cout << ln;
        // int orig = count_common_roads(e);
        // e.pop_back();
        bool sm = 0;
        FOR(k,start,comp[i].size()) {
            int u = comp[i][k];
            if (done[u]) continue;
            e.PB(u);
            // print(s);
            int cur = count_common_roads(e);
            e.pop_back(); // reset single edge
            if (orig < cur) sm = 1, gr.PB(u);
            else if (orig == cur) le.PB(u);
        }
        if (sm || isgold == 0) FORX(y,gr) res[y] = 1;
        else FORX(y,le) res[y] = 1;
        FOR(j,0,cnt-1) e.pop_back(); // reset component edges
    }
    FORX(u,v[s]) done[u.S] = 1;
}

std::vector<int> find_roads(int N, std::vector<int> U, std::vector<int> V) {
    n = N; m = U.size();
    FOR(i,0,m) {
        edges.PB({U[i],V[i]});
        v[U[i]].PB({V[i],i}), v[V[i]].PB({U[i],i});
    }
    FOR(i,0,n) solve(i);
    vector<int> resv;
    FOR(i,0,m) if (res[i]) resv.PB(i);
    // cout << ln;
    // FORX(u,resv) cout << u << " ";
    // cout << ln;
    return resv;
    // cout << "xd\n";
    // FORX(u,res) cout << u << " ";
    // cout << ln;
}

Compilation message (stderr)

simurgh.cpp: In function 'void solve(int)':
simurgh.cpp:11:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 | #define FOR(i,s,n) for (int i = s; i < n; i++)
......
  130 |         FOR(k,start,comp[i].size()) {
      |             ~~~~~~~~~~~~~~~~~~~~~~    
simurgh.cpp:130:9: note: in expansion of macro 'FOR'
  130 |         FOR(k,start,comp[i].size()) {
      |         ^~~

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