| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 543983 |
2022-03-31T18:12:27 Z |
Lobo |
ICC (CEOI16_icc) |
C++14 |
|
309 ms |
800 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];
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));
}
}
}
while(par.size() > 2) {
//coloca randons no primeiro
vector<int> qr[2];
for(int i = 1; i <= n; i++) {
if(find(i) != i) continue;
int colr = rand()%2;
if(vc[colr][i].size() == 0) colr^= 1;
for(auto x : vc[colr][i]) {
qr[rand()%2].pb(x);
}
}
if(qr[0].size() == 0 || qr[1].size() == 0) continue;
int32_t qra[(int32_t) qr[0].size()];
for(int i = 0; i < qr[0].size(); i++) {
qra[i] = qr[0][i];
}
int32_t qrb[(int32_t) qr[1].size()];
for(int i = 0; i < qr[1].size(); i++) {
qrb[i] = qr[1][i];
}
if(query((int32_t) qr[0].size(), (int32_t) qr[1].size(), qra, qrb)) {
//é entre um e outro
// for(auto x : qr[0]) {
// for(auto y : qr[0]) {
// // assert(!(find(x) == find(y) && col[x] != col[y]));
// par.erase(mp(x,y));
// par.erase(mp(y,x));
// }
// }
// for(auto x : qr[1]) {
// for(auto y : qr[1]) {
// // assert(!(find(x) == find(y) && col[x] != col[y]));
// par.erase(mp(x,y));
// par.erase(mp(y,x));
// }
// }
}
else {
for(auto x : qr[0]) {
for(auto y : qr[1]) {
// assert(!(find(x) == find(y) && col[x] != col[y]));
par.erase(mp(x,y));
par.erase(mp(y,x));
}
}
}
}
assert(par.size() != 0);
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);
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;
// }
Compilation message
icc.cpp: In function 'void run(int32_t)':
icc.cpp:83:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
83 | for(int i = 0; i < qr[0].size(); i++) {
| ~~^~~~~~~~~~~~~~
icc.cpp:87:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
87 | for(int i = 0; i < qr[1].size(); i++) {
| ~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
49 ms |
468 KB |
Number of queries more than 3000 out of 1500 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
208 ms |
560 KB |
Number of queries more than 5000 out of 2500 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
237 ms |
800 KB |
Number of queries more than 4500 out of 2250 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
309 ms |
796 KB |
Number of queries more than 4000 out of 2000 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
191 ms |
796 KB |
Number of queries more than 3550 out of 1775 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
229 ms |
724 KB |
Number of queries more than 3250 out of 1625 |
| 2 |
Halted |
0 ms |
0 KB |
- |
