oj.uz

Submission #785308

# Submission time Handle Problem Language Result Execution time Memory
785308 2023-07-17T08:15:38 Z 박상훈(#10022) Raspad (COI17_raspad) C++17
9 / 100
 6000 ms 15228 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

struct DSU1{
	int path[101];

	void init(int n){for (int i=1;i<=n;i++) path[i] = i;}
	int find(int s){
		if (s==path[s]) return s;
		return path[s] = find(path[s]);
	}
	bool merge(int s, int v){
		s = find(s), v = find(v);
		if (s==v) return false;
		path[v] = s;
		return true;
	}
}dsu, dsu3;

struct DSU2{
	int path[101], on[101], cur;
	
	void init(int n){
		cur = 0;
		for (int i=1;i<=n;i++){
			path[i] = i;
			cur += on[i];
			// printf(" %d", on[i]);
		}
		// printf("\n");
	}

	int find(int s){
		if (s==path[s]) return s;
		return path[s] = find(path[s]);
	}

	void merge(int s, int v){
		s = find(s), v = find(v);
		assert(s!=v);

		if (on[s] || on[v]) --cur;
		on[s] &= on[v];

		path[v] = path[s];
	}

	int count(){return cur;}
}dsu2;

struct Data{
	int p, q, t;
	Data(){}
	Data(int _p, int _q, int _t): p(_p), q(_q), t(_t) {}
};

vector<Data> Dat[100100];
char a[100100][55];
int b[100100][55], cnt[100100], to[55];
vector<int> adj[55];

ll simulate(int sx, int cntV, const vector<Data> &Dat){
	int prvT = sx;
	dsu2.init(cntV);

	ll ret = 0;

	for (const auto &[p, q, t]:Dat){
		ret += (ll)(prvT-t) * dsu2.count();
		dsu2.merge(p, q);
		prvT = t;
	}

	ret += (ll)prvT * dsu2.count();
	// printf(" fuck %d\n", dsu2.count());
	return ret;
}

ll solve(int n, int m, char a[100100][55]){
	// init here
	for (int i=1;i<=n;i++){
		Dat[i].clear();
		fill(b[i], b[i]+m+1, 0);
		cnt[i] = 0;
	}

	ll ans = 0;

	for (int i=1;i<=n;i++){
		// printf("calc %d\n", i);
		//init here
		for (int j=1;j<=cnt[i-1];j++){
			adj[j].clear();
			to[j] = 0;
		}

		// get component
		cnt[i] = 0;
		for (int j=1;j<=m;j++) if (a[i][j]=='1'){
			if (j>1 && a[i][j-1]=='1') b[i][j] = b[i][j-1];
			else b[i][j] = ++cnt[i];

			if (b[i-1][j]!=0){
				adj[b[i-1][j]].push_back(b[i][j]);
				to[b[i-1][j]] = b[i][j];
			}
		}

		// for (int j=1;j<=cnt[i-1];j++) printf(" %d", to[j]);
		// printf("\n");

		dsu.init(cnt[i]);

		// merge using (i-1)th row
		for (int j=1;j<=cnt[i-1];j++){
			for (int k=0;k<(int)adj[j].size()-1;j++){
				if (dsu.merge(adj[j][k], adj[j][k+1])){
					Dat[i].emplace_back(adj[j][k], adj[j][k+1], i-1);
				}
			}
		}

		// reindex
		dsu3.init(cnt[i-1]);
		for (auto &[p, q, t]:Dat[i-1]){
			p = dsu3.find(p), q = dsu3.find(q);
			if (!to[p]) swap(p, q);
			dsu3.merge(p, q);
		}

		// merge using x(< i-1)th row
		for (auto &[p, q, t]:Dat[i-1]) if (to[p] && to[q]){
			if (dsu.merge(to[p], to[q])){
				Dat[i].emplace_back(to[p], to[q], t);
			}
		}

		// update ans
		fill(dsu2.on+1, dsu2.on+cnt[i]+1, 1);
		ll val1 = simulate(i, cnt[i], Dat[i]);
		ans += val1;
		// printf(" ok add %lld\n", val1);

		// calc with invalid (i-1)th row component
		fill(dsu2.on+1, dsu2.on+cnt[i-1]+1, 0);
		for (int j=1;j<=cnt[i-1];j++) if (!to[j]) dsu2.on[j] = 1;
		ll val2 = simulate(i-1, cnt[i-1], Dat[i-1]);
		ans += val2 * (n-i+1);

		// printf(" ok add %lld * %d = %lld\n", val2, n-i+1, val2 * (n-i+1));
	}

	return ans;
}


int visited[100100][55], dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};

void dfs(int x, int y, char a[100100][55], int s, int e, int m){
	visited[x][y] = 1;
	for (int k=0;k<4;k++){
		int nx = x + dx[k], ny = y + dy[k];

		if (nx < s || nx > e) continue;
		if (ny < 1 || ny > m) continue;
		if (a[nx][ny]!='1') continue;
		if (visited[nx][ny]) continue;
		dfs(nx, ny, a, s, e, m);
	}
}

ll count_naive(int s, int e, int m, char a[100100][55]){
	ll ans = 0;

	for (int i=s;i<=e;i++){
		fill(visited[i]+1, visited[i]+m+1, 0);
	}

	for (int i=s;i<=e;i++){
		for (int j=1;j<=m;j++) if (!visited[i][j] && a[i][j]=='1'){
			dfs(i, j, a, s, e, m);
			ans++;
		}
	}

	return ans;
}

ll naive(int n, int m, char a[100100][55]){
	ll ans = 0;

	for (int i=1;i<=n;i++){
		for (int j=i;j<=n;j++) ans += count_naive(i, j, m, a);
	}

	return ans;
}

int main(){
	int n, m;
	scanf("%d %d", &n, &m);

	for (int i=1;i<=n;i++) scanf("%s", a[i]+1);

	// printf("%lld\n", solve(n, m, a));
	printf("%lld\n", naive(n, m, a));
}

Compilation message

raspad.cpp: In function 'int main()':
raspad.cpp:203:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  203 |  scanf("%d %d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~~
raspad.cpp:205:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  205 |  for (int i=1;i<=n;i++) scanf("%s", a[i]+1);
      |                         ~~~~~^~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 112 ms 2712 KB Output is correct
3 Correct 55 ms 2872 KB Output is correct
4 Correct 52 ms 2856 KB Output is correct
5 Correct 61 ms 2684 KB Output is correct
6 Correct 87 ms 2692 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 112 ms 2712 KB Output is correct
3 Correct 55 ms 2872 KB Output is correct
4 Correct 52 ms 2856 KB Output is correct
5 Correct 61 ms 2684 KB Output is correct
6 Correct 87 ms 2692 KB Output is correct
7 Execution timed out 6024 ms 2800 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Execution timed out 6061 ms 15228 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 112 ms 2712 KB Output is correct
3 Correct 55 ms 2872 KB Output is correct
4 Correct 52 ms 2856 KB Output is correct
5 Correct 61 ms 2684 KB Output is correct
6 Correct 87 ms 2692 KB Output is correct
7 Execution timed out 6024 ms 2800 KB Time limit exceeded
8 Halted 0 ms 0 KB -