Submission #237292

#	Time	Username	Problem	Language	Result	Execution time	Memory
237292		limabeans	Amusement Park (JOI17_amusement_park)	C++17	0 / 100	50 ms	5260 KiB

Joi

#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++;
    }
}

Ioi

#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) {
//     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<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;
	//cout<<at<<": "<<dst<<endl;
	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) {
	assert(x!=-1);
	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;
	}
	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
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 55
• Subtask 5: 0 / 17