oj.uz

Submission #1081398

# Submission time Handle Problem Language Result Execution time Memory
1081398 2024-08-30T03:50:44 Z thelegendary08 The Ties That Guide Us (CEOI23_incursion) C++17
42 / 100
 279 ms 10796 KB 
#include <bits/stdc++.h>
#include "incursion.h"
#define f0r(i,n) for(int i = 0;i<n;i++)
#define vi vector<int>
using namespace std;
const int mxn = 45005;
bool vis[mxn];
int sts[mxn];
vector<int>adj[mxn];
int dfs(int x, int p){
    vis[x] = 1;
    int cur = 1;
    for(auto u : adj[x]){
        if(u != p){
            cur += dfs(u, x);
        }
    }
    return cur;
}
std::vector<int> mark(std::vector<std::pair<int, int>> F, int safe) {

    safe--;
	int n;

	int two;
	n = F.size() + 1;
	vector<int>dist(n);
	dist[safe] = 0;

	vi deg(n, 0);
	vi degcnt(4, 0);
	f0r(i, n-1){
		adj[--F[i].first].push_back(--F[i].second);
		adj[F[i].second].push_back(F[i].first);
		deg[F[i].first]++;
		deg[F[i].second]++;
	}
	//f0r(i,n)cout<<deg[i]<<' ';
	//cout<<'\n';

	f0r(i,n){
	    if(deg[i] == 2)two = i;
        degcnt[deg[i]]++;
	}

	if(degcnt[3] == 0){
        vi col(n, 0);
        queue<int>q;
        q.push(safe);
        vector<bool>vis(n,0);
        vis[safe] = 1;

        col[safe] = 0;
        while(!q.empty()){
            int cur = q.front();
            q.pop();
            for(auto u : adj[cur]){
                if(vis[u])continue;
                vis[u] = 1;
                dist[u] = dist[cur] + 1;
                col[u] = (col[cur] + 1) % 3;
                q.push(u);
            }
        }
        return col;
	}
	else{
        int thing = dfs(two, -1);
	    vi col(n,0);
        vi par(n);
        par[two] = -1;
        queue<int>q;
        q.push(two);
        while(!q.empty()){
            int cur = q.front();
            q.pop();
            for(auto u : adj[cur]){
                if(u != par[cur]){
                    par[u] = cur;
                    q.push(u);
                }
            }
        }
        //f0r(i,n)cout<<par[i]<<' ';
        //cout<<'\n';

        int now = safe;
        while(now != -1){
            //cout<<now<<'\n';
            col[now] = 1;
            now = par[now];
        }
        //cout<<cur<<'\n';
        //cout<<par[cur]<<'\n';

        //cout<<par[par[par[cur]]]<<'\n';
        return col;


	}


}

void locate(std::vector<std::pair<int, int>> F, int curr, int t) {
	int x;
	vector<int>nxt = {2, 0, 1};
	int n = F.size() + 1;
	vector<bool>vis(n+1, 0);
	vector<int>adj[n+1];
	vi deg(n+1);
	vi degcnt(4, 0);
	f0r(i, n-1){
		adj[F[i].first].push_back(F[i].second);
		adj[F[i].second].push_back(F[i].first);
		deg[F[i].first]++;
		deg[F[i].second]++;
	}
	int two;
	for(int i = 1; i<=n; i++){
        if(deg[i]==2)two = i;
        degcnt[deg[i]]++;
	}
	if(degcnt[3] == 0){
        vis[curr] = 1;
        //queue<int>q;
        //q.push(curr);
        bool found = false;
        int col = t;
        int cur = curr;
        vi cols(n+1, -1);
        cols[curr] = t;
        while(!found){
            bool ok = 0;
            for(auto u : adj[cur]){
                if(vis[u])continue;
                vis[u] = 1;
                x = visit(u);
                cols[u] = x;
                if(x == nxt[cols[cur]]){
                    cur = u;
                    ok = 1;
                    break;
                }
                else{
                    visit(cur);
                }
            }
            if(!ok)return;
        }
	}
	else{
        vi par(n+1);
        par[two] = -1;
        vi d(n+1, 0);

        queue<int>q;
        q.push(two);
        while(!q.empty()){
            int cur = q.front();
            q.pop();
            for(auto u : adj[cur]){
                if(u != par[cur]){
                    par[u] = cur;
                    d[u] = d[cur] + 1;
                    q.push(u);
                }
            }
        }
        //for(int i = 1; i<=n; i++)cout<<d[i]<<' ';
        //cout<<'\n';
        vector<bool>viss(n+1, 0);
        vi sts(n+1, 0);


        priority_queue<pair<int,int>>pq;
        for(int i=1; i<=n;i++){
            if(deg[i] == 1){
                pq.push({d[i], i});
                sts[i] = 1;
                viss[i] = 1;
            }
        }
        while(!pq.empty()){
            int cur = pq.top().second;
            pq.pop();
            //cout<<cur<<'\n';
            //if(par[cur] != -1)sts[par[cur]] += sts[cur];
            if(par[cur] != -1 && !viss[par[cur]]){
                viss[par[cur]] = 1;
                for(auto u : adj[par[cur]]){
                    if(u != par[par[cur]]){
                        sts[par[cur]] += sts[u];
                    }
                }
                pq.push({d[par[cur]], par[cur]});
            }
        }
        //for(int i = 1; i<=n; i++)cout<<sts[i]<<' ';
        //cout<<'\n';
        vi vis(n+1, 0);
        int cur = curr;
        int col = t;
        int x;
        vis[cur] = 1;
        while(col == 0){
            cur = par[cur];
            vis[cur] = 1;
            x = visit(cur);
            col = x;
        }
        bool found = 0;
        while(!found){
            vector<pair<int,int>>thing;
            for(auto u : adj[cur]){
                if(!vis[u] && u != par[cur])thing.push_back({sts[u], u});
            }
            sort(thing.rbegin(), thing.rend());
            bool ok =0;
            for(auto u : thing){
                x = visit(u.second);
                if(x == 0){
                    visit(cur);
                }
                else{
                    cur = u.second;
                    vis[cur] = 1;
                    col = x;
                    ok = 1;
                    break;
                }
            }
            if(!ok)return;
        }

	}



}

Compilation message

incursion.cpp: In function 'std::vector<int> mark(std::vector<std::pair<int, int> >, int)':
incursion.cpp:68:13: warning: unused variable 'thing' [-Wunused-variable]
   68 |         int thing = dfs(two, -1);
      |             ^~~~~
incursion.cpp: In function 'void locate(std::vector<std::pair<int, int> >, int, int)':
incursion.cpp:129:13: warning: unused variable 'col' [-Wunused-variable]
  129 |         int col = t;
      |             ^~~
interface.cpp: In function 'int main()':
interface.cpp:44:55: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   44 |     if(fread(T.data(), sizeof(int), 2 * N - 2, stdin) != 2 * N - 2) exit(0);
      |        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
interface.cpp:50:33: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   50 |         int l = (numbers.size() == N ? N : 0);
      |                  ~~~~~~~~~~~~~~~^~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 2828 KB Partially correct

Subtask #1
12.0 / 30.0

# Verdict Execution time Memory Grader output
1 Partially correct 207 ms 8940 KB Partially correct
2 Partially correct 199 ms 8940 KB Partially correct
3 Partially correct 109 ms 9120 KB Partially correct
4 Partially correct 100 ms 8820 KB Partially correct
5 Partially correct 192 ms 8936 KB Partially correct
6 Partially correct 70 ms 8812 KB Partially correct
7 Partially correct 80 ms 8724 KB Partially correct
8 Partially correct 218 ms 8936 KB Partially correct
9 Partially correct 204 ms 8944 KB Partially correct
10 Partially correct 144 ms 8796 KB Partially correct
11 Partially correct 89 ms 8936 KB Partially correct
12 Partially correct 279 ms 8928 KB Partially correct
13 Partially correct 75 ms 9076 KB Partially correct
14 Partially correct 76 ms 8848 KB Partially correct
15 Partially correct 209 ms 8940 KB Partially correct
16 Partially correct 217 ms 8868 KB Partially correct
17 Partially correct 127 ms 8928 KB Partially correct
18 Partially correct 81 ms 8932 KB Partially correct
19 Partially correct 150 ms 8940 KB Partially correct
20 Partially correct 79 ms 8852 KB Partially correct
21 Partially correct 68 ms 8800 KB Partially correct
22 Partially correct 228 ms 8916 KB Partially correct
23 Partially correct 192 ms 8908 KB Partially correct
24 Partially correct 102 ms 8908 KB Partially correct
25 Partially correct 79 ms 8812 KB Partially correct
26 Partially correct 84 ms 8860 KB Partially correct
27 Partially correct 76 ms 8864 KB Partially correct
28 Partially correct 82 ms 8996 KB Partially correct
29 Partially correct 228 ms 8948 KB Partially correct
30 Partially correct 193 ms 8940 KB Partially correct
31 Partially correct 89 ms 8860 KB Partially correct
32 Partially correct 231 ms 8932 KB Partially correct
33 Partially correct 233 ms 8904 KB Partially correct
34 Partially correct 82 ms 8800 KB Partially correct
35 Partially correct 72 ms 8864 KB Partially correct
36 Partially correct 212 ms 8912 KB Partially correct
37 Partially correct 194 ms 8936 KB Partially correct
38 Partially correct 240 ms 8916 KB Partially correct
39 Partially correct 129 ms 8936 KB Partially correct
40 Partially correct 177 ms 8892 KB Partially correct
41 Partially correct 75 ms 8992 KB Partially correct
42 Partially correct 76 ms 8860 KB Partially correct
43 Partially correct 206 ms 8896 KB Partially correct
44 Partially correct 214 ms 8940 KB Partially correct
45 Partially correct 81 ms 8816 KB Partially correct
46 Partially correct 76 ms 8820 KB Partially correct
47 Partially correct 87 ms 8932 KB Partially correct
48 Partially correct 69 ms 8860 KB Partially correct
49 Partially correct 75 ms 8844 KB Partially correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 9948 KB Correct
2 Correct 93 ms 10264 KB Correct
3 Correct 86 ms 9888 KB Correct
4 Correct 90 ms 10796 KB Correct
5 Correct 137 ms 10768 KB Correct
6 Correct 195 ms 10796 KB Correct
7 Correct 91 ms 9808 KB Correct
8 Correct 82 ms 9804 KB Correct
9 Correct 80 ms 9760 KB Correct
10 Correct 89 ms 9840 KB Correct
11 Correct 80 ms 9988 KB Correct
12 Correct 80 ms 9980 KB Correct
13 Correct 84 ms 9972 KB Correct
14 Correct 60 ms 8500 KB Correct
15 Correct 62 ms 8224 KB Correct
16 Correct 73 ms 9804 KB Correct
17 Correct 83 ms 9884 KB Correct
18 Correct 80 ms 9772 KB Correct
19 Correct 84 ms 9864 KB Correct
20 Correct 64 ms 8120 KB Correct
21 Correct 63 ms 8236 KB Correct
22 Correct 54 ms 8100 KB Correct
23 Correct 64 ms 7988 KB Correct
24 Correct 64 ms 8236 KB Correct
25 Correct 55 ms 7964 KB Correct
26 Correct 73 ms 10100 KB Correct
27 Correct 74 ms 9892 KB Correct
28 Correct 84 ms 10044 KB Correct
29 Correct 86 ms 10044 KB Correct
30 Correct 82 ms 9884 KB Correct
31 Correct 86 ms 10000 KB Correct
32 Correct 81 ms 10300 KB Correct
33 Correct 81 ms 10008 KB Correct
34 Correct 82 ms 10048 KB Correct
35 Correct 86 ms 10020 KB Correct
36 Correct 89 ms 10216 KB Correct
37 Correct 82 ms 10004 KB Correct
38 Correct 81 ms 10008 KB Correct
39 Correct 81 ms 9984 KB Correct
40 Correct 83 ms 9884 KB Correct
41 Correct 88 ms 10012 KB Correct
42 Correct 79 ms 10264 KB Correct
43 Correct 89 ms 10240 KB Correct
44 Correct 84 ms 10044 KB Correct
45 Correct 84 ms 10044 KB Correct
46 Correct 88 ms 10300 KB Correct
47 Correct 84 ms 10272 KB Correct
48 Correct 83 ms 10044 KB Correct
49 Correct 82 ms 9884 KB Correct
50 Correct 82 ms 10104 KB Correct
51 Correct 81 ms 9880 KB Correct
52 Correct 86 ms 10280 KB Correct
53 Correct 81 ms 9860 KB Correct
54 Correct 82 ms 10300 KB Correct
55 Correct 77 ms 9972 KB Correct
56 Correct 82 ms 9952 KB Correct
57 Correct 88 ms 9684 KB Correct
58 Correct 83 ms 9760 KB Correct
59 Correct 78 ms 9888 KB Correct
60 Correct 83 ms 9688 KB Correct
61 Correct 88 ms 9720 KB Correct
62 Correct 80 ms 10020 KB Correct
63 Correct 80 ms 9868 KB Correct
64 Correct 88 ms 9752 KB Correct
65 Correct 80 ms 9724 KB Correct

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 2828 KB Partially correct
2 Partially correct 207 ms 8940 KB Partially correct
3 Partially correct 199 ms 8940 KB Partially correct
4 Partially correct 109 ms 9120 KB Partially correct
5 Partially correct 100 ms 8820 KB Partially correct
6 Partially correct 192 ms 8936 KB Partially correct
7 Partially correct 70 ms 8812 KB Partially correct
8 Partially correct 80 ms 8724 KB Partially correct
9 Partially correct 218 ms 8936 KB Partially correct
10 Partially correct 204 ms 8944 KB Partially correct
11 Partially correct 144 ms 8796 KB Partially correct
12 Partially correct 89 ms 8936 KB Partially correct
13 Partially correct 279 ms 8928 KB Partially correct
14 Partially correct 75 ms 9076 KB Partially correct
15 Partially correct 76 ms 8848 KB Partially correct
16 Partially correct 209 ms 8940 KB Partially correct
17 Partially correct 217 ms 8868 KB Partially correct
18 Partially correct 127 ms 8928 KB Partially correct
19 Partially correct 81 ms 8932 KB Partially correct
20 Partially correct 150 ms 8940 KB Partially correct
21 Partially correct 79 ms 8852 KB Partially correct
22 Partially correct 68 ms 8800 KB Partially correct
23 Partially correct 228 ms 8916 KB Partially correct
24 Partially correct 192 ms 8908 KB Partially correct
25 Partially correct 102 ms 8908 KB Partially correct
26 Partially correct 79 ms 8812 KB Partially correct
27 Partially correct 84 ms 8860 KB Partially correct
28 Partially correct 76 ms 8864 KB Partially correct
29 Partially correct 82 ms 8996 KB Partially correct
30 Partially correct 228 ms 8948 KB Partially correct
31 Partially correct 193 ms 8940 KB Partially correct
32 Partially correct 89 ms 8860 KB Partially correct
33 Partially correct 231 ms 8932 KB Partially correct
34 Partially correct 233 ms 8904 KB Partially correct
35 Partially correct 82 ms 8800 KB Partially correct
36 Partially correct 72 ms 8864 KB Partially correct
37 Partially correct 212 ms 8912 KB Partially correct
38 Partially correct 194 ms 8936 KB Partially correct
39 Partially correct 240 ms 8916 KB Partially correct
40 Partially correct 129 ms 8936 KB Partially correct
41 Partially correct 177 ms 8892 KB Partially correct
42 Partially correct 75 ms 8992 KB Partially correct
43 Partially correct 76 ms 8860 KB Partially correct
44 Partially correct 206 ms 8896 KB Partially correct
45 Partially correct 214 ms 8940 KB Partially correct
46 Partially correct 81 ms 8816 KB Partially correct
47 Partially correct 76 ms 8820 KB Partially correct
48 Partially correct 87 ms 8932 KB Partially correct
49 Partially correct 69 ms 8860 KB Partially correct
50 Partially correct 75 ms 8844 KB Partially correct
51 Correct 91 ms 9948 KB Correct
52 Correct 93 ms 10264 KB Correct
53 Correct 86 ms 9888 KB Correct
54 Correct 90 ms 10796 KB Correct
55 Correct 137 ms 10768 KB Correct
56 Correct 195 ms 10796 KB Correct
57 Correct 91 ms 9808 KB Correct
58 Correct 82 ms 9804 KB Correct
59 Correct 80 ms 9760 KB Correct
60 Correct 89 ms 9840 KB Correct
61 Correct 80 ms 9988 KB Correct
62 Correct 80 ms 9980 KB Correct
63 Correct 84 ms 9972 KB Correct
64 Correct 60 ms 8500 KB Correct
65 Correct 62 ms 8224 KB Correct
66 Correct 73 ms 9804 KB Correct
67 Correct 83 ms 9884 KB Correct
68 Correct 80 ms 9772 KB Correct
69 Correct 84 ms 9864 KB Correct
70 Correct 64 ms 8120 KB Correct
71 Correct 63 ms 8236 KB Correct
72 Correct 54 ms 8100 KB Correct
73 Correct 64 ms 7988 KB Correct
74 Correct 64 ms 8236 KB Correct
75 Correct 55 ms 7964 KB Correct
76 Correct 73 ms 10100 KB Correct
77 Correct 74 ms 9892 KB Correct
78 Correct 84 ms 10044 KB Correct
79 Correct 86 ms 10044 KB Correct
80 Correct 82 ms 9884 KB Correct
81 Correct 86 ms 10000 KB Correct
82 Correct 81 ms 10300 KB Correct
83 Correct 81 ms 10008 KB Correct
84 Correct 82 ms 10048 KB Correct
85 Correct 86 ms 10020 KB Correct
86 Correct 89 ms 10216 KB Correct
87 Correct 82 ms 10004 KB Correct
88 Correct 81 ms 10008 KB Correct
89 Correct 81 ms 9984 KB Correct
90 Correct 83 ms 9884 KB Correct
91 Correct 88 ms 10012 KB Correct
92 Correct 79 ms 10264 KB Correct
93 Correct 89 ms 10240 KB Correct
94 Correct 84 ms 10044 KB Correct
95 Correct 84 ms 10044 KB Correct
96 Correct 88 ms 10300 KB Correct
97 Correct 84 ms 10272 KB Correct
98 Correct 83 ms 10044 KB Correct
99 Correct 82 ms 9884 KB Correct
100 Correct 82 ms 10104 KB Correct
101 Correct 81 ms 9880 KB Correct
102 Correct 86 ms 10280 KB Correct
103 Correct 81 ms 9860 KB Correct
104 Correct 82 ms 10300 KB Correct
105 Correct 77 ms 9972 KB Correct
106 Correct 82 ms 9952 KB Correct
107 Correct 88 ms 9684 KB Correct
108 Correct 83 ms 9760 KB Correct
109 Correct 78 ms 9888 KB Correct
110 Correct 83 ms 9688 KB Correct
111 Correct 88 ms 9720 KB Correct
112 Correct 80 ms 10020 KB Correct
113 Correct 80 ms 9868 KB Correct
114 Correct 88 ms 9752 KB Correct
115 Correct 80 ms 9724 KB Correct
116 Incorrect 95 ms 9860 KB Not correct
117 Halted 0 ms 0 KB -