oj.uz

Submission #785290

# Submission time Handle Problem Language Result Execution time Memory
785290 2023-07-17T08:05:34 Z 박상훈(#10022) Raspad (COI17_raspad) C++17
0 / 100
 57 ms 44084 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;

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]){
	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(m);

		// 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);
				}
			}
		}

		// 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 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));
}

Compilation message

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

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Incorrect 2 ms 2672 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Incorrect 2 ms 2672 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 16256 KB Output is correct
2 Runtime error 57 ms 44084 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Incorrect 2 ms 2672 KB Output isn't correct
3 Halted 0 ms 0 KB -