oj.uz

Submission #374807

# Submission time Handle Problem Language Result Execution time Memory
374807 2021-03-08T08:49:55 Z AriaH Bridges (APIO19_bridges) C++11
44 / 100
 3000 ms 8724 KB 
/** I can do this all day **/

#pragma GCC optimize("O2, unroll-loops")
#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 = 700;

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:40: warning: bad option '-f unroll-loops' to pragma 'optimize' [-Wpragmas]
    3 | #pragma GCC optimize("O2, unroll-loops")
      |                                        ^
bridges.cpp:26:24: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   26 | 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))); }
      |                        ^
bridges.cpp:33:24: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   33 | bool cmp(edge a, edge b)
      |                        ^
bridges.cpp:42:23: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   42 | bool cmp2(int i, int j)
      |                       ^
bridges.cpp:47:14: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   47 | int get(int x) { return (x == par[x]? x : get(par[x])); }
      |              ^
bridges.cpp:49:31: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   49 | inline void unify(int v, int u)
      |                               ^
bridges.cpp:64:18: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   64 | inline void undo()
      |                  ^
bridges.cpp:73:24: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   73 | void solve(int l, int r)
      |                        ^
bridges.cpp:156:10: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
  156 | int main()
      |          ^
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 166 ms 1132 KB Output is correct
4 Correct 8 ms 876 KB Output is correct
5 Correct 94 ms 876 KB Output is correct
6 Correct 90 ms 1004 KB Output is correct
7 Correct 97 ms 876 KB Output is correct
8 Correct 96 ms 876 KB Output is correct
9 Correct 96 ms 876 KB Output is correct
10 Correct 98 ms 876 KB Output is correct
11 Correct 95 ms 876 KB Output is correct
12 Correct 103 ms 1004 KB Output is correct
13 Correct 120 ms 876 KB Output is correct
14 Correct 120 ms 876 KB Output is correct
15 Correct 99 ms 876 KB Output is correct
16 Correct 107 ms 948 KB Output is correct
17 Correct 97 ms 876 KB Output is correct

Subtask #2
0 / 16.0

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

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2665 ms 3984 KB Output is correct
2 Correct 2134 ms 3108 KB Output is correct
3 Correct 2733 ms 3980 KB Output is correct
4 Correct 2617 ms 3912 KB Output is correct
5 Correct 79 ms 2540 KB Output is correct
6 Correct 2752 ms 4096 KB Output is correct
7 Correct 2556 ms 3744 KB Output is correct
8 Correct 2459 ms 3980 KB Output is correct
9 Correct 1259 ms 4260 KB Output is correct
10 Correct 1228 ms 4204 KB Output is correct
11 Correct 1482 ms 3972 KB Output is correct
12 Correct 1399 ms 3868 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2398 ms 6896 KB Output is correct
2 Correct 73 ms 3900 KB Output is correct
3 Correct 263 ms 5868 KB Output is correct
4 Correct 155 ms 6776 KB Output is correct
5 Correct 1514 ms 8620 KB Output is correct
6 Correct 2387 ms 8116 KB Output is correct
7 Correct 1486 ms 8552 KB Output is correct
8 Correct 1150 ms 6168 KB Output is correct
9 Correct 1134 ms 6380 KB Output is correct
10 Correct 1136 ms 7012 KB Output is correct
11 Correct 1810 ms 7180 KB Output is correct
12 Correct 1751 ms 7148 KB Output is correct
13 Correct 1789 ms 8228 KB Output is correct
14 Correct 1436 ms 8700 KB Output is correct
15 Correct 1486 ms 8416 KB Output is correct
16 Correct 2381 ms 8332 KB Output is correct
17 Correct 2416 ms 8036 KB Output is correct
18 Correct 2425 ms 8244 KB Output is correct
19 Correct 2420 ms 8144 KB Output is correct
20 Correct 2009 ms 8520 KB Output is correct
21 Correct 2020 ms 8544 KB Output is correct
22 Correct 2277 ms 8724 KB Output is correct
23 Correct 1432 ms 8320 KB Output is correct

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3060 ms 4552 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 166 ms 1132 KB Output is correct
4 Correct 8 ms 876 KB Output is correct
5 Correct 94 ms 876 KB Output is correct
6 Correct 90 ms 1004 KB Output is correct
7 Correct 97 ms 876 KB Output is correct
8 Correct 96 ms 876 KB Output is correct
9 Correct 96 ms 876 KB Output is correct
10 Correct 98 ms 876 KB Output is correct
11 Correct 95 ms 876 KB Output is correct
12 Correct 103 ms 1004 KB Output is correct
13 Correct 120 ms 876 KB Output is correct
14 Correct 120 ms 876 KB Output is correct
15 Correct 99 ms 876 KB Output is correct
16 Correct 107 ms 948 KB Output is correct
17 Correct 97 ms 876 KB Output is correct
18 Execution timed out 3060 ms 4552 KB Time limit exceeded
19 Halted 0 ms 0 KB -