oj.uz

Submission #374805

# Submission time Handle Problem Language Result Execution time Memory
374805 2021-03-08T08:43:49 Z AriaH Bridges (APIO19_bridges) C++11
13 / 100
 3000 ms 5348 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 = 1;

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);
		}
	}
	reverse(all(WTF));
	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]);
		for(int _ = 0; _ < SZ(hist); _++)
		{
			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 876 ms 1324 KB Output is correct
4 Correct 150 ms 1132 KB Output is correct
5 Correct 188 ms 1004 KB Output is correct
6 Correct 179 ms 1132 KB Output is correct
7 Correct 176 ms 1132 KB Output is correct
8 Correct 192 ms 1260 KB Output is correct
9 Correct 181 ms 1004 KB Output is correct
10 Correct 193 ms 1004 KB Output is correct
11 Correct 195 ms 1260 KB Output is correct
12 Correct 192 ms 1132 KB Output is correct
13 Correct 219 ms 1132 KB Output is correct
14 Correct 221 ms 1260 KB Output is correct
15 Correct 220 ms 1132 KB Output is correct
16 Correct 170 ms 1004 KB Output is correct
17 Correct 176 ms 1132 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3040 ms 3304 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 3069 ms 2576 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3092 ms 5348 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 3040 ms 3304 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 876 ms 1324 KB Output is correct
4 Correct 150 ms 1132 KB Output is correct
5 Correct 188 ms 1004 KB Output is correct
6 Correct 179 ms 1132 KB Output is correct
7 Correct 176 ms 1132 KB Output is correct
8 Correct 192 ms 1260 KB Output is correct
9 Correct 181 ms 1004 KB Output is correct
10 Correct 193 ms 1004 KB Output is correct
11 Correct 195 ms 1260 KB Output is correct
12 Correct 192 ms 1132 KB Output is correct
13 Correct 219 ms 1132 KB Output is correct
14 Correct 221 ms 1260 KB Output is correct
15 Correct 220 ms 1132 KB Output is correct
16 Correct 170 ms 1004 KB Output is correct
17 Correct 176 ms 1132 KB Output is correct
18 Execution timed out 3040 ms 3304 KB Time limit exceeded
19 Halted 0 ms 0 KB -