oj.uz

Submission #374806

# Submission time Handle Problem Language Result Execution time Memory
374806 2021-03-08T08:48:42 Z AriaH Bridges (APIO19_bridges) C++11
30 / 100
 3000 ms 5652 KB 
/** I can do this all day **/

#pragma GCC optimize("O2")
#include <bits/stdc++.h>
using namespace std;

typedef long long                   ll;
typedef long double                 ld;
typedef pair<int,int>               pii;
typedef pair<ll,ll>                 pll;
#define all(x)                      (x).begin(),(x).end()
#define F                           first
#define S                           second
#define Mp                          make_pair
#define SZ(x)			    		(int)x.size()
#define fast_io                     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io                     freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);

const int N = 1e5 + 10;
const ll mod = 1e9 + 7;
const ll mod2 = 998244353;
const ll inf = 8e18;
const int LOG = 22;
const int B = 320;

ll pw(ll a , ll b, ll M)  { return (!b ? 1 : (b & 1 ? (a * pw(a * a % M, b / 2, M)) % M : pw(a * a % M, b / 2, M))); }

struct edge
{
	int u, v, w, id;
} org[N], E[N];

bool cmp(edge a, edge b)
{
	return a.w > b.w;
}

int n, m, q, tp[N], fir[N], sec[N], change[N], par[N], sz[N], Ans[N];

vector < pii > hist;

bool cmp2(int i, int j)
{
	return sec[i] > sec[j];
}

int get(int x) { return (x == par[x]? x : get(par[x])); }

inline void unify(int v, int u)
{
	///printf("merging v = %d u = %d\n", v, u);
	v = get(v), u = get(u);
	if(v == u)
	{
		hist.push_back(Mp(0, 0));
		return;
	}
	if(sz[u] > sz[v]) swap(u, v);
	par[u] = v;
	sz[v] += sz[u];
	hist.push_back(Mp(u, v));
}

inline void undo()
{
	if(hist.empty()) return;
	pii cu = hist.back();
	hist.pop_back();
	par[cu.F] = cu.F;
	sz[cu.S] -= sz[cu.F];
}

void solve(int l, int r)
{
	///printf("baze = %d %d\n", l, r);
	if(l > r) return;
	hist.clear();
	for(int i = 1; i <= n; i ++) par[i] = i, sz[i] = 1;
	memset(change, 0, sizeof change);
	vector < int > WTF;
	for(int i = l; i <= r; i ++)
	{
		if(tp[i] == 1)
		{
			if(change[fir[i]]) continue;
			change[fir[i]] = 1;
			WTF.push_back(i);
		}
	}
	for(int i = 1; i <= m; i ++) E[i] = org[i];
	sort(E + 1, E + m + 1, cmp);
	/*for(int i = 1; i <= m; i ++)
	{
		printf("%d %d %d %d\n", E[i].v, E[i].u, E[i].w, change[E[i].id]);
	}
	*/
	vector < int > Q;
	for(int i = l; i <= r; i ++)
	{
		if(tp[i] == 1) continue;
		Q.push_back(i);
	}
	sort(all(Q), cmp2);
	int last = 1;
	for(auto i : Q)
	{
		
		while(last <= m && sec[i] <= E[last].w)
		{
			if(change[E[last].id] == 0)
			{
				///printf("merged v = %d u = %d id = %d\n", E[last].v, E[last].u, E[last].id);
				unify(E[last].v, E[last].u);
			}
			last ++;
		}
		hist.clear();
		///printf("i = %d fir = %d sec = %d last = %d sz = %d\n", i, fir[i], sec[i], last, sz[get(fir[i])]);
		set < int > used;
		for(int j = i; j >= l; j --)
		{
			if(tp[j] == 1)
			{
				if(used.count(fir[j]) > 0) continue;
				used.insert(fir[j]);
				if(sec[j] < sec[i]) continue;
				unify(org[fir[j]].v, org[fir[j]].u);
			}
		}
		for(auto cu : WTF)
		{
			if(cu <= i) continue;
			if(org[fir[cu]].w < sec[i]) continue;
			unify(org[fir[cu]].v, org[fir[cu]].u);

		}
		Ans[i] = sz[get(fir[i])];
		///printf("Ans = %d\n", Ans[i]);
		int Sz = SZ(hist);
		for(int _ = 0; _ < Sz; _++)
		{
			undo();
			///printf("undo\n");
		}
	}
	for(int i = l; i <= r; i ++)
	{
		if(tp[i] == 1)
		{
			org[fir[i]].w = sec[i];
		}
	}

}

int main()
{
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= m; i ++)
	{
		scanf("%d%d%d", &org[i].v, &org[i].u, &org[i].w);
		org[i].id = i;
	}
	scanf("%d", &q);
	for(int i = 1; i <= q; i ++)
	{
		scanf("%d%d%d", &tp[i], &fir[i], &sec[i]);
		if(i % B == 0)
		{
			solve(i - B + 1, i);
		}
	}
	solve(q / B * B + 1, q);
	for(int i = 1; i <= q; i ++)
	{
		if(tp[i] == 2) printf("%d\n", Ans[i]);
	}
    return 0;
}

/** test corner cases(n = 1?) watch for overflow or minus indices **/

Compilation message

bridges.cpp: In function 'int main()':
bridges.cpp:158:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  158 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
bridges.cpp:161:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  161 |   scanf("%d%d%d", &org[i].v, &org[i].u, &org[i].w);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:164:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  164 |  scanf("%d", &q);
      |  ~~~~~^~~~~~~~~~
bridges.cpp:167:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  167 |   scanf("%d%d%d", &tp[i], &fir[i], &sec[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 748 KB Output is correct
2 Correct 1 ms 748 KB Output is correct
3 Correct 80 ms 1004 KB Output is correct
4 Correct 7 ms 876 KB Output is correct
5 Correct 53 ms 876 KB Output is correct
6 Correct 51 ms 876 KB Output is correct
7 Correct 55 ms 1004 KB Output is correct
8 Correct 64 ms 876 KB Output is correct
9 Correct 55 ms 876 KB Output is correct
10 Correct 54 ms 876 KB Output is correct
11 Correct 54 ms 876 KB Output is correct
12 Correct 55 ms 876 KB Output is correct
13 Correct 64 ms 876 KB Output is correct
14 Correct 63 ms 876 KB Output is correct
15 Correct 56 ms 876 KB Output is correct
16 Correct 55 ms 876 KB Output is correct
17 Correct 54 ms 876 KB Output is correct

Subtask #2
0 / 16.0

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

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2246 ms 3856 KB Output is correct
2 Correct 1159 ms 4588 KB Output is correct
3 Correct 2269 ms 5320 KB Output is correct
4 Correct 2227 ms 5216 KB Output is correct
5 Correct 63 ms 3820 KB Output is correct
6 Correct 2271 ms 5356 KB Output is correct
7 Correct 2213 ms 5404 KB Output is correct
8 Correct 2170 ms 5236 KB Output is correct
9 Correct 1674 ms 5652 KB Output is correct
10 Correct 1643 ms 5612 KB Output is correct
11 Correct 1741 ms 5356 KB Output is correct
12 Correct 1711 ms 5380 KB Output is correct

Subtask #4
0 / 14.0

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

Subtask #5
0 / 13.0

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

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 748 KB Output is correct
2 Correct 1 ms 748 KB Output is correct
3 Correct 80 ms 1004 KB Output is correct
4 Correct 7 ms 876 KB Output is correct
5 Correct 53 ms 876 KB Output is correct
6 Correct 51 ms 876 KB Output is correct
7 Correct 55 ms 1004 KB Output is correct
8 Correct 64 ms 876 KB Output is correct
9 Correct 55 ms 876 KB Output is correct
10 Correct 54 ms 876 KB Output is correct
11 Correct 54 ms 876 KB Output is correct
12 Correct 55 ms 876 KB Output is correct
13 Correct 64 ms 876 KB Output is correct
14 Correct 63 ms 876 KB Output is correct
15 Correct 56 ms 876 KB Output is correct
16 Correct 55 ms 876 KB Output is correct
17 Correct 54 ms 876 KB Output is correct
18 Execution timed out 3073 ms 4372 KB Time limit exceeded
19 Halted 0 ms 0 KB -