oj.uz

Submission #794853

# Submission time Handle Problem Language Result Execution time Memory
794853 2023-07-27T01:33:04 Z Magikarp4000 Simurgh (IOI17_simurgh) C++17
0 / 100
 2 ms 2644 KB 
#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, res;
vector<PII> v[MAXN];
bool z[MAXN], z1[MAXN];

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);
    }
}

std::vector<int> find_roads(int N, std::vector<int> U, std::vector<int> V) {
    n = N; m = U.size();
    FOR(i,0,m) v[U[i]].PB({V[i],i}), v[V[i]].PB({U[i],i});
    FOR(i,0,n) {
        if (v[i].size() == 1) {
            int u = v[i][0].S;
            z1[u] = 1;
            if (!z[u]) {
                z[u] = 1;
                res.PB(u);
            }
        }
    }
    FOR(i,0,n) {
        e.clear();
        FOR(j,0,n) {
            p[j] = j, sz[j] = 1;
        }
        FOR(j,0,m) {
            if (z1[j] || (U[j] != i && V[j] != i)) unite(U[j],V[j],j);
        }
        vector<int> w,w1;
        bool done = 0;
        FORX(u,v[i]) {
            if (!z1[u.S]) {
                e.PB(u.S);
                if (!z[u.S]) w.PB(u.S);
                z[u.S] = done = 1;
                break;
            }
        }
        int orig = count_common_roads(e);
        if (done) e.pop_back();
        bool sm = 0;
        FORX(u,v[i]) {
            if (z[u.S]) continue;   
            z[u.S] = 1;
            e.PB(u.S);
            // cout << i << " " << u.F << ": ";
            // FORX(y,e) cout << y << " ";
            // cout << ln;
            int cur = count_common_roads(e);
            e.pop_back();
            if (cur > orig) sm = 1, w1.PB(u.S);
            else if (cur == orig) w.PB(u.S);
        }
        if (sm == 0) FORX(u,w) res.PB(u);
        else FORX(u,w1) res.PB(u); 
    }
    // cout << "xd\n";
    // FORX(u,res) cout << u << " ";
    // cout << ln;
    return res;
}

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2644 KB WA in grader: NO
2 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2644 KB WA in grader: NO
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2644 KB WA in grader: NO
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB correct
2 Incorrect 1 ms 2644 KB WA in grader: NO
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2644 KB WA in grader: NO
2 Halted 0 ms 0 KB -