oj.uz

Submission #64241

# Submission time Handle Problem Language Result Execution time Memory
64241 2018-08-03T14:46:16 Z reality Amusement Park (JOI17_amusement_park) C++17
100 / 100
 966 ms 242792 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 = 1e4 + 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 dfs(int node,int prev,set < int > nodes,set < pii > degs) {
    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];
            }
        }
}

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 = 1e4 + 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);
    POS = P;
    DFS(P,-1);
    answer |= (1ll << color[P]) * V;
    for (auto it : e)
    	answer |= (1ll << color[it]) * Move(it);
    return answer;
}

Compilation message

Joi.cpp: In function 'void dfs(int, int, std::set<int>, std::set<std::pair<int, int> >)':
Joi.cpp:69:17: warning: 'v' may be used uninitialized in this function [-Wmaybe-uninitialized]
                 ++deg[v];
                 ^~~~~~~~

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 9 ms 2288 KB Output is correct
2 Correct 12 ms 2628 KB Output is correct
3 Correct 18 ms 3200 KB Output is correct
4 Correct 11 ms 3912 KB Output is correct
5 Correct 12 ms 4260 KB Output is correct
6 Correct 16 ms 4296 KB Output is correct
7 Correct 22 ms 5352 KB Output is correct
8 Correct 17 ms 5376 KB Output is correct
9 Correct 19 ms 5376 KB Output is correct
10 Correct 14 ms 5376 KB Output is correct
11 Correct 15 ms 5376 KB Output is correct
12 Correct 10 ms 5376 KB Output is correct
13 Correct 19 ms 5376 KB Output is correct
14 Correct 18 ms 5376 KB Output is correct
15 Correct 25 ms 5376 KB Output is correct
16 Correct 19 ms 5376 KB Output is correct
17 Correct 19 ms 5376 KB Output is correct
18 Correct 19 ms 5376 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 515 ms 10052 KB Output is correct
2 Correct 463 ms 10612 KB Output is correct
3 Correct 404 ms 10680 KB Output is correct
4 Correct 437 ms 10744 KB Output is correct
5 Correct 692 ms 114512 KB Output is correct
6 Correct 673 ms 114544 KB Output is correct
7 Correct 539 ms 114544 KB Output is correct
8 Correct 552 ms 114544 KB Output is correct
9 Correct 577 ms 114544 KB Output is correct
10 Correct 392 ms 114544 KB Output is correct
11 Correct 457 ms 114544 KB Output is correct
12 Correct 358 ms 114544 KB Output is correct
13 Correct 408 ms 114544 KB Output is correct
14 Correct 480 ms 114544 KB Output is correct
15 Correct 383 ms 114544 KB Output is correct
16 Correct 408 ms 114544 KB Output is correct
17 Correct 487 ms 114544 KB Output is correct
18 Correct 450 ms 114544 KB Output is correct
19 Correct 399 ms 114544 KB Output is correct
20 Correct 538 ms 127140 KB Output is correct
21 Correct 558 ms 127208 KB Output is correct
22 Correct 591 ms 127208 KB Output is correct
23 Correct 610 ms 127208 KB Output is correct
24 Correct 587 ms 127208 KB Output is correct
25 Correct 611 ms 127208 KB Output is correct
26 Correct 733 ms 127208 KB Output is correct
27 Correct 647 ms 127208 KB Output is correct
28 Correct 610 ms 127208 KB Output is correct
29 Correct 576 ms 127208 KB Output is correct
30 Correct 556 ms 127208 KB Output is correct
31 Correct 13 ms 127208 KB Output is correct
32 Correct 17 ms 127208 KB Output is correct
33 Correct 15 ms 127208 KB Output is correct
34 Correct 12 ms 127208 KB Output is correct
35 Correct 14 ms 127208 KB Output is correct
36 Correct 13 ms 127208 KB Output is correct
37 Correct 8 ms 127208 KB Output is correct
38 Correct 8 ms 127208 KB Output is correct
39 Correct 9 ms 127208 KB Output is correct
40 Correct 12 ms 127208 KB Output is correct
41 Correct 14 ms 127208 KB Output is correct
42 Correct 8 ms 127208 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 127208 KB Output is correct
2 Correct 12 ms 127208 KB Output is correct
3 Correct 12 ms 127208 KB Output is correct
4 Correct 137 ms 127208 KB Output is correct
5 Correct 128 ms 127208 KB Output is correct
6 Correct 152 ms 127208 KB Output is correct
7 Correct 121 ms 127208 KB Output is correct
8 Correct 139 ms 127208 KB Output is correct
9 Correct 806 ms 242748 KB Output is correct
10 Correct 800 ms 242792 KB Output is correct
11 Correct 866 ms 242792 KB Output is correct
12 Correct 10 ms 242792 KB Output is correct
13 Correct 9 ms 242792 KB Output is correct
14 Correct 9 ms 242792 KB Output is correct
15 Correct 7 ms 242792 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 448 ms 242792 KB Output is correct
2 Correct 395 ms 242792 KB Output is correct
3 Correct 408 ms 242792 KB Output is correct
4 Correct 460 ms 242792 KB Output is correct
5 Correct 770 ms 242792 KB Output is correct
6 Correct 540 ms 242792 KB Output is correct
7 Correct 649 ms 242792 KB Output is correct
8 Correct 582 ms 242792 KB Output is correct
9 Correct 618 ms 242792 KB Output is correct
10 Correct 375 ms 242792 KB Output is correct
11 Correct 395 ms 242792 KB Output is correct
12 Correct 370 ms 242792 KB Output is correct
13 Correct 361 ms 242792 KB Output is correct
14 Correct 472 ms 242792 KB Output is correct
15 Correct 450 ms 242792 KB Output is correct
16 Correct 472 ms 242792 KB Output is correct
17 Correct 532 ms 242792 KB Output is correct
18 Correct 477 ms 242792 KB Output is correct
19 Correct 455 ms 242792 KB Output is correct
20 Correct 574 ms 242792 KB Output is correct
21 Correct 579 ms 242792 KB Output is correct
22 Correct 709 ms 242792 KB Output is correct
23 Correct 648 ms 242792 KB Output is correct
24 Correct 712 ms 242792 KB Output is correct
25 Correct 819 ms 242792 KB Output is correct
26 Correct 780 ms 242792 KB Output is correct
27 Correct 758 ms 242792 KB Output is correct
28 Correct 643 ms 242792 KB Output is correct
29 Correct 649 ms 242792 KB Output is correct
30 Correct 602 ms 242792 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 505 ms 242792 KB Output is correct
2 Correct 498 ms 242792 KB Output is correct
3 Correct 525 ms 242792 KB Output is correct
4 Correct 455 ms 242792 KB Output is correct
5 Correct 966 ms 242792 KB Output is correct
6 Correct 669 ms 242792 KB Output is correct
7 Correct 572 ms 242792 KB Output is correct
8 Correct 641 ms 242792 KB Output is correct
9 Correct 718 ms 242792 KB Output is correct
10 Correct 459 ms 242792 KB Output is correct
11 Correct 429 ms 242792 KB Output is correct
12 Correct 399 ms 242792 KB Output is correct
13 Correct 374 ms 242792 KB Output is correct
14 Correct 378 ms 242792 KB Output is correct
15 Correct 450 ms 242792 KB Output is correct
16 Correct 489 ms 242792 KB Output is correct
17 Correct 447 ms 242792 KB Output is correct
18 Correct 414 ms 242792 KB Output is correct
19 Correct 519 ms 242792 KB Output is correct
20 Correct 508 ms 242792 KB Output is correct
21 Correct 558 ms 242792 KB Output is correct
22 Correct 593 ms 242792 KB Output is correct
23 Correct 534 ms 242792 KB Output is correct
24 Correct 567 ms 242792 KB Output is correct
25 Correct 669 ms 242792 KB Output is correct
26 Correct 566 ms 242792 KB Output is correct
27 Correct 616 ms 242792 KB Output is correct
28 Correct 609 ms 242792 KB Output is correct
29 Correct 575 ms 242792 KB Output is correct
30 Correct 548 ms 242792 KB Output is correct
31 Correct 14 ms 242792 KB Output is correct
32 Correct 14 ms 242792 KB Output is correct
33 Correct 15 ms 242792 KB Output is correct
34 Correct 12 ms 242792 KB Output is correct
35 Correct 11 ms 242792 KB Output is correct
36 Correct 10 ms 242792 KB Output is correct
37 Correct 11 ms 242792 KB Output is correct
38 Correct 10 ms 242792 KB Output is correct
39 Correct 6 ms 242792 KB Output is correct
40 Correct 11 ms 242792 KB Output is correct
41 Correct 13 ms 242792 KB Output is correct
42 Correct 9 ms 242792 KB Output is correct