oj.uz

답안 #67107

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
67107 2018-08-13T10:43:52 Z reality Snowy Roads (JOI16_snowy) C++17
0 / 100
 19 ms 2400 KB 
#include "Anyalib.h"
#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'\n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define vii vector < pii >
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()
template < class P , class Q > ostream& operator<<(ostream& stream, pair < P , Q > v){ stream << "(" << v.fi << ',' << v.se << ")"; return stream;}
template < class T > ostream& operator<<(ostream& stream, const vector<T> v){ stream << "[ "; for (int i=0; i<(int)v.size(); i++) stream << v[i] << " "; stream << "]"; return stream;}
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}

static const int N = 1024;

static int n;

static vector < pii > g[N];

static int P[N][N];

static int fr[N];

static int coef[N];

static int lf[N];

static int rg[N];

static vii e;

static int Time = 0;

static void dfs(int node = 0,int index = 0) {
	++Time;
	lf[index] = Time;
	fr[node] = Time;
	coef[Time] = 1;
	for (auto it : g[node])
		if (it.se != index)
			dfs(it.fi,it.se);
	++Time;
	rg[index] = Time;
	coef[Time] = -1;
}

void InitAnya(int NN, int A[] , int B[]) {
	n = NN;
	for (int i = 0;i < n - 1;++i) {
		g[A[i]].pb(mp(B[i],i + 1));
		g[B[i]].pb(mp(A[i],i + 1));
		P[A[i]][B[i]] = P[B[i]][A[i]] = i + 1;
	}
	dfs();
}

static int sum[N];

void Anya(int C[]) {
	for (int i = 0;i <= n + n;++i)
		sum[i] = 0;
	for (int i = 1;i < n;++i) {
		sum[lf[i]] = C[i - 1];
		sum[rg[i]] = -C[i - 1];
	}
	for (int i = 1;i <= n + n;++i)
		sum[i] += sum[i - 1];
	for (int i = 0;i < n - 1;++i)
		Save(i,C[i]);
	for (int i = 0;i * 20 < n + n;++i) {
		int ed = min(n + n,(i + 1) * 20);
		for (int t = 0;t < 10;++t)
			Save(n - 1 + t + i * 10,(sum[ed] >> t) & 1);
	}
}

#include "Borislib.h"
#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'\n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define vii vector < pii >
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()
template < class P , class Q > ostream& operator<<(ostream& stream, pair < P , Q > v){ stream << "(" << v.fi << ',' << v.se << ")"; return stream;}
template < class T > ostream& operator<<(ostream& stream, const vector<T> v){ stream << "[ "; for (int i=0; i<(int)v.size(); i++) stream << v[i] << " "; stream << "]"; return stream;}
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}

static const int N = 1024;

static int n;

static vector < pii > g[N];

static int P[N][N];

static int fr[N];

static int coef[N];

static int lf[N];

static int rg[N];

static int ac[N];

static vii e;

static int Time = 0;

static void dfs(int node = 0,int index = 0) {
	++Time;
	lf[index] = Time;
	ac[Time] = index - 1;
	fr[node] = Time;
	coef[Time] = 1;
	for (auto it : g[node])
		if (it.se != index)
			dfs(it.fi,it.se);
	++Time;
	ac[Time] = index - 1;
	rg[index] = Time;
	coef[Time] = -1;
}

void InitBoris(int NN , int A[] , int B[]) {
  	n = NN;
	for (int i = 0;i < n - 1;++i) {
		g[A[i]].pb(mp(B[i],i + 1));
		g[B[i]].pb(mp(A[i],i + 1));
		P[A[i]][B[i]] = P[B[i]][A[i]] = i + 1;
	}
	dfs();
}

int Boris(int node) {
	int need = fr[node];
	int pos,beg;
	for (int i = 0;i * 20 < n + n;++i) {
		int ed = min(n + n,(i + 1) * 20);
		if (abs(need - ed) <= 10) {
			pos = ed;
			beg = i * 10 + n - 1;
			break;
		}
	}
	assert(abs(pos - need) <= 10);
	int ans = 0;
	for (int i = 0;i < 10;++i)
		assert(0 <= beg + i && beg + i < 1000),ans += Ask(beg + i) * (1 << i);
	while (pos < need) {
		++pos;
		if (ac[pos] >= 0)
			ans += Ask(ac[pos]) * coef[pos];
	}
	while (pos > need) {
		if (ac[pos] >= 0)
			ans -= Ask(ac[pos]) * coef[pos];
		--pos;
	}
	return ans;
}

Compilation message

Boris.cpp: In function 'int Boris(int)':
Boris.cpp:70:10: warning: 'beg' may be used uninitialized in this function [-Wmaybe-uninitialized]
  int pos,beg;
          ^~~
Boris.cpp:70:6: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
  int pos,beg;
      ^~~

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 920 KB Output is correct
2 Runtime error 4 ms 1248 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 13 ms 1816 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 18 ms 2132 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 19 ms 2400 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -