oj.uz

Submission #544015

# Submission time Handle Problem Language Result Execution time Memory
544015 2022-03-31T19:56:19 Z Lobo ICC (CEOI16_icc) C++17
7 / 100
 343 ms 804 KB 
#include "icc.h"
#include<bits/stdc++.h>
using namespace std;

const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()

const int maxn = 110;

// int edgset[maxn][maxn];
// int qtddd;
// void setRoad(int u, int v) {
//     cout << u << " " << v << endl;

//     if(--qtddd != 0) {
//         int x,y; cin >> x >> y;
//         edgset[x][y] = edgset[y][x] = 1;
//     }
// }

// int query(int sza, int szb, int32_t a[], int32_t b[]) {
//     int ans = 0;
//     for(int i = 0; i < sza; i++) {
//         for(int j = 0; j < szb; j++) {
//             ans|= edgset[a[i]][b[j]];
//         }
//     }
//     return ans;
// }


int n, ds[maxn], col[maxn], g[maxn][maxn];
vector<int> vc[2][maxn];

int find(int v) {
    if(v == ds[v]) return v;
    return ds[v] = find(ds[v]);
}

void run(int32_t N) {
    srand(time(0));
    n = N;
    for(int i = 1; i <= n; i++) {
        ds[i] = i;
        vc[0][i].pb(i);
        col[i] = 0;
    }

    for(int qt = 0; qt < n-1; qt++) {
        set<pair<int,int>> par;
        for(int i = 1; i <= n; i++) {
            for(int j = i+1; j <= n; j++) {
                if(find(i) != find(j)) {
                    par.insert(mp(i,j));
                }
            }
        }

        

        assert(!(par.size() == 0 && qt <= 40));

        for(auto X : par) {
            int u = X.fr;
            int v = X.sc;
            int32_t qra[1]; qra[0] = u;
            int32_t qrb[1]; qrb[0] = v;

            // cout << qt << " " << u << " " << v << " ---- " << query(1,1,qra,qrb) << endl;

            if(query(1,1,qra,qrb)) {
                //coloca o v no u
                int pu = find(u);
                int pv = find(v);
                // assert(pu != pv);
                ds[pv] = pu;
                //os caras com col igual a col[v] ficam com col[u]^1
                int colv = col[v];
                for(auto x : vc[colv][pv]) {
                    vc[col[u]^1][pu].pb(x);
                    col[x] = col[u]^1;
                }
                for(auto x : vc[colv^1][pv]) {
                    vc[col[u]][pu].pb(x);
                    col[x] = col[u];
                }
                setRoad(u,v);
                g[u][v] = g[v][u] = 1;
                break;
            }
        }
    }
}

// int32_t main() {
//     ios::sync_with_stdio(false); cin.tie(0);

//     freopen("in.in", "r", stdin);
//     // freopen("out.out", "w", stdout);

//     int N; cin >> N;
//     qtddd = N-1;
//     int x,y; cin >> x >> y;
//     edgset[x][y] = edgset[y][x] = 1;
//     run(N);

//     // int v = find(1);
//     // for(auto x : vc[0][v]) {
//     //     cout << x << " ";
//     // }cout << endl;
//     // for(auto x : vc[1][v]) {
//     //     cout << x << " ";
//     // }cout << endl;
// }

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 520 KB Ok! 1015 queries used.
2 Correct 42 ms 528 KB Ok! 1009 queries used.

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 263 ms 576 KB Number of queries more than 5000 out of 2500
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 343 ms 796 KB Number of queries more than 4500 out of 2250
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 327 ms 792 KB Number of queries more than 4000 out of 2000
2 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 288 ms 804 KB Number of queries more than 3550 out of 1775
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 281 ms 796 KB Number of queries more than 3250 out of 1625
2 Halted 0 ms 0 KB -