oj.uz

답안 #652647

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
652647 2022-10-23T15:25:02 Z MilosMilutinovic CEOI16_icc (CEOI16_icc) C++14
0 / 100
 3 ms 596 KB 
#include "icc.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef basic_string<int> BI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}());
const ll mod=998244353;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head

const int N=105;
int n,vis[N];
VI cc[N],g[N];

/*void setRoad(int a,int b) {
//	printf("ROAD: %d %d\n",a,b);
	g[a].pb(b);
	g[b].pb(a);
}*/

void addRoad(int a,int b) {
	setRoad(a,b);
	g[a].pb(b);
	g[b].pb(a);
}

void dfs(int v,int r) {
	cc[r].pb(v);
	vis[v]=1;
	for (int u:g[v]) if (!vis[u]) dfs(u,r);
}

int qquery(VI a,VI b) {
	int sza=SZ(a),szb=SZ(b);
	int aa[sza],bb[szb];
	rep(i,0,sza) aa[i]=a[i];
	rep(i,0,szb) bb[i]=b[i];
//	rep(i,0,sza) assert(aa[i]>=1&&aa[i]<=n);
//	rep(i,0,sza) assert(bb[i]>=1&&bb[i]<=n);
	return query(sza,szb,aa,bb);
}

VI merge(VI x,VI y) {
	VI v;
	for (int i:x) v.pb(i);
	for (int i:y) v.pb(i);
	return v;
}

VI gen(VI v) {
	VI ret;
	for (int i:v) for (int j:cc[i]) ret.pb(j);
	return ret;
}

void findRoad(int r0,int r1) {
	int x=-1,y=-1;
	int l=0,r=SZ(cc[r1])-1;
	while (l<=r) {
		int mid=l+r>>1;
		VI vv;
		rep(i,0,mid+1) vv.pb(cc[r1][i]);
		if (qquery(cc[r0],vv)) y=cc[r1][mid],r=mid-1;
		else l=mid+1;
	}
//	assert(y!=-1);
	l=0,r=SZ(cc[r0])-1;
	while (l<=r) {
		int mid=l+r>>1;
		VI vv;
		rep(i,0,mid+1) vv.pb(cc[r0][i]);
		if (qquery(vv,{y})) x=cc[r0][mid],r=mid-1;
		else l=mid+1;
	}
	addRoad(x,y);
}

void rec(VI v) {
	if (SZ(v)==2) {
		findRoad(v[0],v[1]);
		return;
	}
	assert(SZ(v)>2);
	VI vx[3];
	rep(i,0,SZ(v)) vx[i%3].pb(v[i]);
	int r1=qquery(gen(vx[0]),gen(vx[1]));
	if (r1) {
		rec(merge(gen(vx[0]),gen(vx[1])));
		return;
	}
	int r2=qquery(gen(vx[0]),gen(vx[2]));
	if (r2) {
		rec(merge(gen(vx[0]),gen(vx[2])));
		return;
	}
	rec(merge(gen(vx[1]),gen(vx[2])));
}

void run(int n) {
	::n=n;
	rep(it,1,n) {
		rep(i,1,n+1) {
			cc[i].clear();
			vis[i]=0;
		}
		VI v;
		rep(i,1,n+1) {
			if (!vis[i]) {
				dfs(i,i);
				v.pb(i);
			}
		}
		rec(v);
	}
}

Compilation message

icc.cpp: In function 'void findRoad(int, int)':
icc.cpp:74:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   74 |   int mid=l+r>>1;
      |           ~^~
icc.cpp:83:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   83 |   int mid=l+r>>1;
      |           ~^~

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 468 KB Query cities not in range [1, n]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 468 KB Query cities not in range [1, n]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 468 KB Query cities not in range [1, n]
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 596 KB Query cities not in range [1, n]
2 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 468 KB Query cities not in range [1, n]
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 488 KB Query cities not in range [1, n]
2 Halted 0 ms 0 KB -