oj.uz

Submission #237294

# Submission time Handle Problem Language Result Execution time Memory
237294 2020-06-05T17:54:40 Z limabeans Amusement Park (JOI17_amusement_park) C++17
0 / 100
 43 ms 6188 KB 
#include "Joi.h"
#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl




typedef long long ll;
const int maxn = 10005;


static vector<int> g[maxn];
static vector<int> path;
static bool viz[maxn];

// void MessageBoard(int attr, int msg) {
// }

static void dfs(int at) {
    path.push_back(at);
    viz[at]=true;
    for (int to: g[at]) {
	if (viz[to]) continue;
	dfs(to);
    }
    if (path.back() != at) {
	path.push_back(at);
    }
}

void Joi(int n, int m, int a[], int b[], long long x, int t) {
    for (int i=0; i<=n; i++) {
	g[i].clear();
    }
    path.clear();
    memset(viz,false,sizeof(viz));
    
    for (int i=0; i<m; i++) {
	g[a[i]].push_back(b[i]);
	g[b[i]].push_back(a[i]);
    }
    for (int i=0; i<n; i++) {
	sort(g[i].begin(), g[i].end());
    }
    dfs(0);
    memset(viz,false,sizeof(viz));
    ll j=0;
    for (int at: path) {
	if (viz[at]) continue;
	viz[at]=true;
	MessageBoard(at, x>>j&1);
	j++;
    }
}

#include "Ioi.h"
#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl




typedef long long ll;
const ll mod = 1e9+7;
const int maxn = 10005;
const int inf = 1e9;

static set<int> g[maxn];
static vector<int> path;
static bool viz[maxn];
int nodes;


// int Move(int dest) {
//     cout<<"Move: "<<dest<<endl;
//     return 1;
// }

static void dfs(int at) {
    path.push_back(at);
    viz[at]=true;
    for (int to: g[at]) {
	if (viz[to]) continue;
	dfs(to);
    }
    if (path.back() != at) {
	path.push_back(at);
    }
}


vector<int> dij(int src) {
    int n = nodes;
    vector<int> dist(n, inf);
    vector<int> par(n, -1);
    dist[src] = 0;

    queue<int> qq;
    qq.push(src);
    while (qq.size()) {
	int at = qq.front();
	qq.pop();
	for (int to: g[at]) {
	    if (dist[to]>1+dist[at]) {
		dist[to]=1+dist[at];
		par[to]=at;
		qq.push(to);
	    }
	}
    }

    vector<int> res;
    int at = 0;
    while (at != src) {
	res.push_back(at);
	at=par[at];
    }
    reverse(res.begin(), res.end());
    return res;
}


long long Ioi(int n, int m, int a[], int b[], int p, int v, int t) {
    nodes = n;
    for (int i=0; i<=n; i++) {
	g[i].clear();
    }
    path.clear();
    memset(viz,false,sizeof(viz));
    
    for (int i=0; i<m; i++) {
	g[a[i]].insert(b[i]);
	g[b[i]].insert(a[i]);
    }

    int cur=p;
    vector<int> pathto0 = dij(cur);
    for (int x: pathto0) {
	assert(g[cur].count(x));
	assert(x!=-1);
	Move(x);
	cur=x;
    }

    assert(cur==0);
    int to=*g[cur].begin();
    Move(to);
    cur=to;

    dfs(0);
    memset(viz,false,sizeof(viz));

    
    ll j=0;
    ll ans = 0;
    for (int nxt: path) {
	//assert(g[cur].count(nxt));
	ll val = Move(nxt);
	cur=nxt;
	if (viz[nxt]) {
	    continue;
	}
	viz[nxt]=true;
	if (j>=60) {
	    continue;
	}

	ans = ans | (val<<j);
	j++;
    }
    
    return ans;
}



// int main() {
//     //long long Ioi(int n, int m, int a[], int b[], int p, int v, int t) {
//     int a[] = {0,1,2,2};
//     int b[] = {1,2,0,3};
//     ll res  = Ioi(4,4,a,b,3,0,0);
//     watch(res);
//     return 0;
// }

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 1548 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 43 ms 6180 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1768 KB Output is correct
2 Correct 10 ms 1800 KB Output is correct
3 Incorrect 10 ms 1636 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Incorrect 41 ms 6116 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 41 ms 6188 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -