oj.uz

Submission #619940

# Submission time Handle Problem Language Result Execution time Memory
619940 2022-08-02T17:26:05 Z Ozy Simurgh (IOI17_simurgh) C++17
30 / 100
 176 ms 3548 KB 
#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define rep(i,a,b) for (int i = (a); i <= (b); i++)
#define repa(i,a,b) for (int i = (a); i >= (b); i--)
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "

#define MAX 250
#define des first
#define id second

//gurpo reaal
int ufreal[MAX+2];
int greal;
vector<int> goldenway;

//grupo de prueba
int uf[MAX+2],vis[MAX+2],M[MAX+2];
int grupos;
vector<int> prueba,defaul,query,res;

//variables
int n,m;
vector<int> u,v;
vector<pair<int, int> > hijos[MAX+2];


int sube(int a, int uf[]) {
    if (uf[a] == a) return a;
    uf[a] = sube(uf[a],uf);
    return uf[a];
}

bool une(int a, int b, int uf[]) {

    a = sube(a,uf);
    b = sube(b,uf);

    if (a == b) return false;

    if (b < a) swap(a,b);
    uf[b] = a;
    return true;
}


std::vector<int> find_roads(int N, std::vector<int> U, std::vector<int> V) {
    n = N;
    swap(u,U);
    swap(v,V);
    m = u.size();

    rep(i,0,m-1) {
        hijos[u[i]].push_back({v[i],i});
        hijos[v[i]].push_back({u[i],i});
    }

    rep(i,0,n-1) ufreal[i] = i;
    greal = n;

    rep(act,0,n-1) {

        //borro todo
        rep(i,0,n-1) uf[i] = i;
        prueba.clear();

        rep(i,0,m-1) {
            if (u[i] == act || v[i] == act) continue;
            if (une(u[i],v[i],uf)) {
                grupos--;
                prueba.push_back(i);
            }
        }

        //debbug
        //debug(act);
        //for (auto p : prueba) cout << p << ' ';
        //cout << endl;

        defaul.clear();
        res.clear();
        rep(i,0,n-1) {
            vis[i] = -1;
            M[i] = -1;
        }

        int k;
        for (auto h : hijos[act]) {
            k = sube(h.des,uf);
            if (vis[k] == -1) {
                vis[k] = h.id;
                defaul.push_back(h.id);
            }
        }

        int num;
        for (auto h : hijos[act]) {
            k = sube(h.des,uf);
            query.clear();
            for (auto x : prueba) query.push_back(x);
            for (auto d : defaul) {
                if (d == vis[k]) query.push_back(h.id);
                else query.push_back(d);
            }

            num = count_common_roads(query);
            M[k] = max(num , M[k]);
            res.push_back(num);
        }

        num = hijos[act].size();
        rep(i,0,num-1) {
            k = sube(hijos[act][i].des,uf);
            if (res[i] == M[k]) {
                if (une(act,hijos[act][i].des,ufreal)) {
                    goldenway.push_back(hijos[act][i].id);
                    greal--;
                }
            }
        }

    }

    return goldenway;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB correct
2 Correct 1 ms 312 KB correct
3 Correct 1 ms 212 KB correct
4 Correct 1 ms 316 KB correct
5 Correct 1 ms 212 KB correct
6 Correct 1 ms 212 KB correct
7 Correct 0 ms 212 KB correct
8 Correct 1 ms 308 KB correct
9 Correct 1 ms 212 KB correct
10 Correct 0 ms 212 KB correct
11 Correct 0 ms 312 KB correct
12 Correct 0 ms 212 KB correct
13 Correct 1 ms 212 KB correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB correct
2 Correct 1 ms 312 KB correct
3 Correct 1 ms 212 KB correct
4 Correct 1 ms 316 KB correct
5 Correct 1 ms 212 KB correct
6 Correct 1 ms 212 KB correct
7 Correct 0 ms 212 KB correct
8 Correct 1 ms 308 KB correct
9 Correct 1 ms 212 KB correct
10 Correct 0 ms 212 KB correct
11 Correct 0 ms 312 KB correct
12 Correct 0 ms 212 KB correct
13 Correct 1 ms 212 KB correct
14 Correct 4 ms 340 KB correct
15 Correct 4 ms 316 KB correct
16 Correct 4 ms 340 KB correct
17 Correct 3 ms 340 KB correct
18 Correct 1 ms 340 KB correct
19 Correct 3 ms 340 KB correct
20 Correct 3 ms 340 KB correct
21 Correct 3 ms 368 KB correct
22 Correct 3 ms 340 KB correct
23 Correct 2 ms 340 KB correct
24 Correct 2 ms 340 KB correct
25 Correct 1 ms 212 KB correct
26 Correct 2 ms 340 KB correct
27 Correct 2 ms 340 KB correct
28 Correct 1 ms 212 KB correct
29 Correct 1 ms 212 KB correct
30 Correct 2 ms 340 KB correct
31 Correct 2 ms 340 KB correct
32 Correct 2 ms 340 KB correct
33 Correct 2 ms 340 KB correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB correct
2 Correct 1 ms 312 KB correct
3 Correct 1 ms 212 KB correct
4 Correct 1 ms 316 KB correct
5 Correct 1 ms 212 KB correct
6 Correct 1 ms 212 KB correct
7 Correct 0 ms 212 KB correct
8 Correct 1 ms 308 KB correct
9 Correct 1 ms 212 KB correct
10 Correct 0 ms 212 KB correct
11 Correct 0 ms 312 KB correct
12 Correct 0 ms 212 KB correct
13 Correct 1 ms 212 KB correct
14 Correct 4 ms 340 KB correct
15 Correct 4 ms 316 KB correct
16 Correct 4 ms 340 KB correct
17 Correct 3 ms 340 KB correct
18 Correct 1 ms 340 KB correct
19 Correct 3 ms 340 KB correct
20 Correct 3 ms 340 KB correct
21 Correct 3 ms 368 KB correct
22 Correct 3 ms 340 KB correct
23 Correct 2 ms 340 KB correct
24 Correct 2 ms 340 KB correct
25 Correct 1 ms 212 KB correct
26 Correct 2 ms 340 KB correct
27 Correct 2 ms 340 KB correct
28 Correct 1 ms 212 KB correct
29 Correct 1 ms 212 KB correct
30 Correct 2 ms 340 KB correct
31 Correct 2 ms 340 KB correct
32 Correct 2 ms 340 KB correct
33 Correct 2 ms 340 KB correct
34 Incorrect 176 ms 1524 KB WA in grader: NO
35 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB correct
2 Correct 1 ms 212 KB correct
3 Runtime error 18 ms 3548 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB correct
2 Correct 1 ms 312 KB correct
3 Correct 1 ms 212 KB correct
4 Correct 1 ms 316 KB correct
5 Correct 1 ms 212 KB correct
6 Correct 1 ms 212 KB correct
7 Correct 0 ms 212 KB correct
8 Correct 1 ms 308 KB correct
9 Correct 1 ms 212 KB correct
10 Correct 0 ms 212 KB correct
11 Correct 0 ms 312 KB correct
12 Correct 0 ms 212 KB correct
13 Correct 1 ms 212 KB correct
14 Correct 4 ms 340 KB correct
15 Correct 4 ms 316 KB correct
16 Correct 4 ms 340 KB correct
17 Correct 3 ms 340 KB correct
18 Correct 1 ms 340 KB correct
19 Correct 3 ms 340 KB correct
20 Correct 3 ms 340 KB correct
21 Correct 3 ms 368 KB correct
22 Correct 3 ms 340 KB correct
23 Correct 2 ms 340 KB correct
24 Correct 2 ms 340 KB correct
25 Correct 1 ms 212 KB correct
26 Correct 2 ms 340 KB correct
27 Correct 2 ms 340 KB correct
28 Correct 1 ms 212 KB correct
29 Correct 1 ms 212 KB correct
30 Correct 2 ms 340 KB correct
31 Correct 2 ms 340 KB correct
32 Correct 2 ms 340 KB correct
33 Correct 2 ms 340 KB correct
34 Incorrect 176 ms 1524 KB WA in grader: NO
35 Halted 0 ms 0 KB -