oj.uz

Submission #374810

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

#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#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 = 800;

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:3: warning: ignoring #pragma comment  [-Wunknown-pragmas]
    3 | #pragma comment(linker, "/stack:200000000")
      | 
bridges.cpp: In function 'int main()':
bridges.cpp:160:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  160 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
bridges.cpp:163:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  163 |   scanf("%d%d%d", &org[i].v, &org[i].u, &org[i].w);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:166:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  166 |  scanf("%d", &q);
      |  ~~~~~^~~~~~~~~~
bridges.cpp:169:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  169 |   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 202 ms 1132 KB Output is correct
4 Correct 10 ms 876 KB Output is correct
5 Correct 111 ms 876 KB Output is correct
6 Correct 98 ms 876 KB Output is correct
7 Correct 108 ms 1152 KB Output is correct
8 Correct 107 ms 876 KB Output is correct
9 Correct 100 ms 876 KB Output is correct
10 Correct 108 ms 876 KB Output is correct
11 Correct 108 ms 964 KB Output is correct
12 Correct 110 ms 1004 KB Output is correct
13 Correct 129 ms 876 KB Output is correct
14 Correct 136 ms 876 KB Output is correct
15 Correct 111 ms 1004 KB Output is correct
16 Correct 108 ms 1132 KB Output is correct
17 Correct 105 ms 876 KB Output is correct

Subtask #2
0 / 16.0

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

Subtask #3
0 / 17.0

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

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2252 ms 6516 KB Output is correct
2 Correct 95 ms 2540 KB Output is correct
3 Correct 245 ms 4076 KB Output is correct
4 Correct 168 ms 4992 KB Output is correct
5 Correct 1606 ms 6812 KB Output is correct
6 Correct 2221 ms 6552 KB Output is correct
7 Correct 1606 ms 6824 KB Output is correct
8 Correct 1094 ms 4652 KB Output is correct
9 Correct 1096 ms 4736 KB Output is correct
10 Correct 1102 ms 5220 KB Output is correct
11 Correct 1669 ms 5472 KB Output is correct
12 Correct 1659 ms 5500 KB Output is correct
13 Correct 1699 ms 6552 KB Output is correct
14 Correct 1547 ms 6996 KB Output is correct
15 Correct 1622 ms 6760 KB Output is correct
16 Correct 2233 ms 6212 KB Output is correct
17 Correct 2234 ms 6284 KB Output is correct
18 Correct 2256 ms 6560 KB Output is correct
19 Correct 2225 ms 6380 KB Output is correct
20 Correct 1911 ms 6780 KB Output is correct
21 Correct 1899 ms 6748 KB Output is correct
22 Correct 2163 ms 7152 KB Output is correct
23 Correct 1441 ms 6624 KB Output is correct

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3051 ms 4204 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 202 ms 1132 KB Output is correct
4 Correct 10 ms 876 KB Output is correct
5 Correct 111 ms 876 KB Output is correct
6 Correct 98 ms 876 KB Output is correct
7 Correct 108 ms 1152 KB Output is correct
8 Correct 107 ms 876 KB Output is correct
9 Correct 100 ms 876 KB Output is correct
10 Correct 108 ms 876 KB Output is correct
11 Correct 108 ms 964 KB Output is correct
12 Correct 110 ms 1004 KB Output is correct
13 Correct 129 ms 876 KB Output is correct
14 Correct 136 ms 876 KB Output is correct
15 Correct 111 ms 1004 KB Output is correct
16 Correct 108 ms 1132 KB Output is correct
17 Correct 105 ms 876 KB Output is correct
18 Execution timed out 3051 ms 4204 KB Time limit exceeded
19 Halted 0 ms 0 KB -