oj.uz

Submission #237280

# Submission time Handle Problem Language Result Execution time Memory
237280 2020-06-05T17:19:59 Z limabeans Amusement Park (JOI17_amusement_park) C++17
0 / 100
 48 ms 4972 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) {
// }

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 vector<int> g[maxn];
static vector<int> path;
static bool viz[maxn];
int nodes;


// int Move(int dest) {
//     return 0;
// }

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<bool> done(n, false);
    vector<int> par(n, -1);
    dist[src] = 0;
    set<pair<int,int>> st;
    for (int i=0; i<n; i++) {
	st.insert({dist[i], i});
    }

    while (!st.empty()) {
	auto cur=*st.begin();
	st.erase(st.begin());
	int dst = cur.first;
	int at = cur.second;
	if (done[at]) continue;
	dist[at] = dst;
	done[at] = true;
	for (int to: g[at]) {
	    if (dst+1<dist[to]) {
		assert(st.count({dist[to],to}));
		st.erase({dist[to],to});
		dist[to]=1+dist[at];
		st.insert({dist[to],to});
		par[to] = at;
	    }
	}
    }

    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]].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());
    }

    vector<int> pathto0 = dij(p);
    assert((p==0 && pathto0.empty()) || (pathto0.back() == 0));
    for (int x: pathto0) {
	Move(x);
    }

    Move(g[0].front());


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

    
    ll j=0;
    ll ans = 0;
    for (int nxt: path) {
	ll val = Move(nxt);
	if (viz[nxt]) {
	    continue;
	}
	if (j>=60) {
	    continue;
	}

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

Subtask #1
0 / 8.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 48 ms 4636 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 1508 KB Output is correct
2 Correct 10 ms 1540 KB Output is correct
3 Incorrect 10 ms 1536 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

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

Subtask #5
0 / 17.0

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