oj.uz

Submission #64238

# Submission time Handle Problem Language Result Execution time Memory
64238 2018-08-03T14:38:28 Z reality Amusement Park (JOI17_amusement_park) C++17
8 / 100
 1507 ms 279816 KB 
#include "Joi.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 mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()
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;}
const int N = 1e6 + 5;

const int C = 60;

static vi g[N];

static set < int > G[N];

static int color[N];

static int f[N];

static int deg[N];

static int get(int k) {
    return k == f[k] ? k : f[k] = get(f[k]);
}

static int n;

static void connect(set < int > st) {
    int cnt = 0;
    for (auto u : st)
        for (auto v : st)
            if (u < v && G[u].count(v))
                ++cnt;
    assert(cnt + 1 == st.size());
}

static void dfs(int node,int prev,set < int > nodes,set < pii > degs) {
    set < int > col;
    for (auto it : nodes)
        col.insert(color[it]);
    assert(!col.count(-1));
    assert(col.size() == C);
    connect(nodes);
    for (auto it : g[node])
        if (it != prev) {
            if (nodes.count(it))
                dfs(it,node,nodes,degs);
            else {
                set < int > new_nodes;
                set < pii > new_degs;
                for (auto w : nodes)
                    new_nodes.insert(w);
                int u,v;
                auto low = degs.begin();
                if (low->se == node) 
                    ++low;
                assert(low->fi == 1);
                u = low->se;
                for (auto w : nodes)
                    if (G[u].count(w)) {
                        v = w;
                        break;
                    }
                assert(G[u].count(v));
                new_nodes.erase(u);
                new_nodes.insert(it);
                color[it] = color[u];
                --deg[u];
                --deg[v];
                ++deg[node];
                ++deg[it];
                for (auto it : new_nodes)
                    new_degs.insert(mp(deg[it],it));
                dfs(it,node,new_nodes,new_degs);
                ++deg[u];
                ++deg[v];
                --deg[node];
                --deg[it];
            }
        }
}

void Joi(int N, int M, int A[], int B[], long long X, int T) {
    n = N;
    for (int i = 0;i < n;++i)
  		f[i] = i,color[i] = -1;
  	for (int i = 0;i < M;++i) {
  		if (get(A[i]) == get(B[i]))
  			continue;
  		g[A[i]].pb(B[i]);
  		g[B[i]].pb(A[i]);
  	    G[A[i]].insert(B[i]);
        G[B[i]].insert(A[i]);
    	f[get(A[i])] = get(B[i]);
  	}
    set < int > nodes;
    set < pii > degs;
    queue < int > Q;
    int TT = -1;
    Q.push(0);
    while (!Q.empty()) {
        int node = Q.front();
        Q.pop();
        nodes.insert(node);
        color[node] = ++TT;
        if (nodes.size() == C)
            break;
        for (auto it : g[node])
            if (!nodes.count(it)) {
                Q.push(it);
            }
    }
    for (auto u : nodes)
        for (auto v : g[u])
            if (nodes.count(v) && u < v)
                ++deg[u],++deg[v];
    for (auto it : nodes)
        degs.insert(mp(deg[it],it));
    dfs(0,-1,nodes,degs);
    for (int i = 0;i < n;++i)
        MessageBoard(i,(X >> color[i]) & 1);
}

#include "Ioi.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 mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()
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;}
const int N = 1e6 + 5;

const int C = 60;

static vi g[N];

static set < int > G[N];

static int color[N];

static int f[N];

static int deg[N];

static int get(int k) {
    return k == f[k] ? k : f[k] = get(f[k]);
}

static int POS;

static int n;

static int was[N];

static void dfs(int node,int prev,set < int > nodes,set < pii > degs) {
    if (node == POS) {
    	POS = -1;
    	for (auto it : nodes)
    		was[it] = 1;
    }
    for (auto it : g[node])
        if (it != prev) {
            if (nodes.count(it))
                dfs(it,node,nodes,degs);
            else {
                set < int > new_nodes;
                set < pii > new_degs;
                for (auto w : nodes)
                    new_nodes.insert(w);
                int u,v;
                auto low = degs.begin();
                if (low->se == node) 
                    ++low;
                u = low->se;
                for (auto w : nodes)
                    if (G[u].count(w)) {
                        v = w;
                        break;
                    }
                new_nodes.erase(u);
                new_nodes.insert(it);
                color[it] = color[u];
                --deg[u];
                --deg[v];
                ++deg[node];
                ++deg[it];
                for (auto it : new_nodes)
                    new_degs.insert(mp(deg[it],it));
                dfs(it,node,new_nodes,new_degs);
                ++deg[u];
                ++deg[v];
                --deg[node];
                --deg[it];
            }
        }
}

static ll answer = 0;

vi e;

static void DFS(int node,int prev) {
	if (prev != -1) {
		e.pb(node);
	}
	for (auto it : g[node])
		if (it != prev && was[it]) {
			DFS(it,node);
			e.pb(node);
		}
}

long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
    n = N;
    for (int i = 0;i < n;++i)
  		f[i] = i,color[i] = -1;
  	for (int i = 0;i < M;++i) {
  		if (get(A[i]) == get(B[i]))
  			continue;
  		g[A[i]].pb(B[i]);
  		g[B[i]].pb(A[i]);
  	    G[A[i]].insert(B[i]);
        G[B[i]].insert(A[i]);
    	f[get(A[i])] = get(B[i]);
  	}
    set < int > nodes;
    set < pii > degs;
    queue < int > Q;
    int TT = -1;
    Q.push(0);
    while (!Q.empty()) {
        int node = Q.front();
        Q.pop();
        nodes.insert(node);
        color[node] = ++TT;
        if (nodes.size() == C)
            break;
        for (auto it : g[node])
            if (!nodes.count(it)) {
                Q.push(it);
            }
    }
    POS = P;
    for (auto u : nodes)
        for (auto v : g[u])
            if (nodes.count(v) && u < v)
                ++deg[u],++deg[v];
    for (auto it : nodes)
        degs.insert(mp(deg[it],it));
    dfs(0,-1,nodes,degs);
    assert(POS == -1);
    assert(accumulate(was,was + N,0) == C);
    POS = P;
    DFS(P,-1);
    answer |= (1ll << color[P]) * V;
    assert(G[P].count(e[0]));
    for (int i = 0;i + 1 < e.size();++i)
    	assert(G[e[i]].count(e[i + 1]));
    for (auto it : e)
    	answer |= (1ll << color[it]) * Move(it);
    return answer;
}

Compilation message

In file included from /usr/include/c++/7/cassert:44:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:33,
                 from Joi.cpp:2:
Joi.cpp: In function 'void connect(std::set<int>)':
Joi.cpp:44:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     assert(cnt + 1 == st.size());
            ~~~~~~~~^~~~~~~~~~~~

Ioi.cpp: In function 'long long int Ioi(int, int, int*, int*, int, int, int)':
Ioi.cpp:144:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0;i + 1 < e.size();++i)
                    ~~~~~~^~~~~~~~~~
Ioi.cpp: In function 'void dfs(int, int, std::set<int>, std::set<std::pair<int, int> >)':
Ioi.cpp:78:17: warning: 'v' may be used uninitialized in this function [-Wmaybe-uninitialized]
                 ++deg[v];
                 ^~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 142052 KB Output is correct
2 Correct 145 ms 142288 KB Output is correct
3 Correct 160 ms 142832 KB Output is correct
4 Correct 158 ms 143544 KB Output is correct
5 Correct 147 ms 144056 KB Output is correct
6 Correct 145 ms 144056 KB Output is correct
7 Correct 176 ms 145640 KB Output is correct
8 Correct 150 ms 145640 KB Output is correct
9 Correct 182 ms 145640 KB Output is correct
10 Correct 160 ms 145640 KB Output is correct
11 Correct 155 ms 145640 KB Output is correct
12 Correct 135 ms 145640 KB Output is correct
13 Correct 178 ms 145640 KB Output is correct
14 Correct 157 ms 145640 KB Output is correct
15 Correct 174 ms 145640 KB Output is correct
16 Correct 189 ms 145640 KB Output is correct
17 Correct 170 ms 145640 KB Output is correct
18 Correct 181 ms 145640 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1172 ms 150048 KB Output is correct
2 Correct 1060 ms 150576 KB Output is correct
3 Correct 1140 ms 150576 KB Output is correct
4 Correct 1081 ms 150576 KB Output is correct
5 Runtime error 1507 ms 279816 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
6 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 148 ms 279816 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Runtime error 1124 ms 279816 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 1154 ms 279816 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
2 Halted 0 ms 0 KB -