oj.uz

Submission #605118

# Submission time Handle Problem Language Result Execution time Memory
605118 2022-07-25T13:14:24 Z Carmel_Ab1 ICC (CEOI16_icc) C++17
7 / 100
 522 ms 908 KB 
/*
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
 */
#include<bits/stdc++.h>
#include "icc.h"

//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

//using namespace __gnu_pbds;
using namespace std;

typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int>vi;
typedef vector<vector<int>>vvi;
typedef vector<ll>vl;
typedef vector<vl> vvl;
typedef pair<int,int>pi;
typedef pair<ll,ll> pl;
typedef vector<pl> vpl;
typedef vector<ld> vld;
typedef pair<ld,ld> pld;
typedef vector<pi> vpi;


#define all(x) x.begin(),x.end()
#define YES out("YES")
#define NO out("NO")
#define out(x){cout << x << "\n"; return;}
#define outfl(x){cout << x << endl;return;}
#define GLHF ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define print(x){for(auto ait:x) cout << ait << " "; cout << "\n";}
#define pb push_back
#define umap unordered_map

int query(vi a,vi b){
    int* A=new int[a.size()],*B=new int[b.size()];
    for(int i=0; i<a.size(); i++)
        A[i]=a[i];
    for(int i=0; i<b.size(); i++)
        B[i]=b[i];

    return query(a.size(),b.size(),A,B);
}

vi par;
void init(int n){
    par.resize(n+1);
    iota(all(par),0);
}
int get(int x){
    return par[x]=(x==par[x]?x:get(par[x]));
}
void unite(int u,int v){
    par[get(u)]=get(v);
}

void run(int n){
    vpi E;
    for(int i=1; i<=n; i++)
        for(int j=i+1; j<=n; j++)
            E.pb({i,j});
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    shuffle(all(E),rng);
    init(n);

    for(int rep=0; rep<n-1; rep++)
        for(auto[u,v]:E){
            if(get(u)==get(v))continue;
            if(!query({u},{v}))continue;
            unite(u,v);
            setRoad(u,v);
        }
}
/*
 4
1 3
1 4
2 4
 */

Compilation message

icc.cpp: In function 'int query(vi, vi)':
icc.cpp:42:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for(int i=0; i<a.size(); i++)
      |                  ~^~~~~~~~~
icc.cpp:44:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     for(int i=0; i<b.size(); i++)
      |                  ~^~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 468 KB Ok! 1104 queries used.
2 Correct 45 ms 552 KB Ok! 1108 queries used.

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 276 ms 780 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 522 ms 908 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 491 ms 760 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 435 ms 712 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 400 ms 768 KB Number of queries more than 3250 out of 1625
2 Halted 0 ms 0 KB -