oj.uz

Submission #374809

# Submission time Handle Problem Language Result Execution time Memory
374809 2021-03-08T08:52:06 Z AriaH Bridges (APIO19_bridges) C++11
27 / 100
 3000 ms 7080 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 = 1000;

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 246 ms 1132 KB Output is correct
4 Correct 11 ms 876 KB Output is correct
5 Correct 122 ms 1004 KB Output is correct
6 Correct 115 ms 876 KB Output is correct
7 Correct 127 ms 876 KB Output is correct
8 Correct 127 ms 876 KB Output is correct
9 Correct 117 ms 876 KB Output is correct
10 Correct 129 ms 876 KB Output is correct
11 Correct 128 ms 876 KB Output is correct
12 Correct 132 ms 1004 KB Output is correct
13 Correct 153 ms 876 KB Output is correct
14 Correct 152 ms 876 KB Output is correct
15 Correct 135 ms 1024 KB Output is correct
16 Correct 123 ms 876 KB Output is correct
17 Correct 126 ms 1004 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3043 ms 3972 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 3074 ms 3488 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1840 ms 6312 KB Output is correct
2 Correct 104 ms 2540 KB Output is correct
3 Correct 196 ms 4076 KB Output is correct
4 Correct 141 ms 5092 KB Output is correct
5 Correct 1298 ms 6760 KB Output is correct
6 Correct 1790 ms 6344 KB Output is correct
7 Correct 1324 ms 6836 KB Output is correct
8 Correct 910 ms 4432 KB Output is correct
9 Correct 909 ms 4716 KB Output is correct
10 Correct 914 ms 5268 KB Output is correct
11 Correct 1374 ms 5484 KB Output is correct
12 Correct 1357 ms 5496 KB Output is correct
13 Correct 1391 ms 6256 KB Output is correct
14 Correct 1316 ms 7080 KB Output is correct
15 Correct 1302 ms 6864 KB Output is correct
16 Correct 1806 ms 6472 KB Output is correct
17 Correct 1852 ms 6252 KB Output is correct
18 Correct 1857 ms 6252 KB Output is correct
19 Correct 1880 ms 6220 KB Output is correct
20 Correct 1616 ms 6656 KB Output is correct
21 Correct 1597 ms 6616 KB Output is correct
22 Correct 1782 ms 7012 KB Output is correct
23 Correct 1205 ms 6476 KB Output is correct

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3043 ms 3972 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 246 ms 1132 KB Output is correct
4 Correct 11 ms 876 KB Output is correct
5 Correct 122 ms 1004 KB Output is correct
6 Correct 115 ms 876 KB Output is correct
7 Correct 127 ms 876 KB Output is correct
8 Correct 127 ms 876 KB Output is correct
9 Correct 117 ms 876 KB Output is correct
10 Correct 129 ms 876 KB Output is correct
11 Correct 128 ms 876 KB Output is correct
12 Correct 132 ms 1004 KB Output is correct
13 Correct 153 ms 876 KB Output is correct
14 Correct 152 ms 876 KB Output is correct
15 Correct 135 ms 1024 KB Output is correct
16 Correct 123 ms 876 KB Output is correct
17 Correct 126 ms 1004 KB Output is correct
18 Execution timed out 3043 ms 3972 KB Time limit exceeded
19 Halted 0 ms 0 KB -