oj.uz

답안 #237293

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
237293 2020-06-05T17:50:59 Z limabeans Amusement Park (JOI17_amusement_park) C++17
0 / 100
 51 ms 9804 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<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]].insert(b[i]);
	g[b[i]].insert(a[i]);
    }

    vector<int> pathto0 = dij(p);
    assert((p==0 && pathto0.empty()) || (pathto0.back() == 0));
    for (int x: pathto0) {
	assert(g[v].count(x));
	assert(x!=-1);
	Move(x);
	v=x;
    }

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

    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.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 55.0

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

Subtask #5
0 / 17.0

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