oj.uz

Submission #930037

# Submission time Handle Problem Language Result Execution time Memory
930037 2024-02-18T09:43:47 Z pan Rigged Roads (NOI19_riggedroads) C++17
37 / 100
 319 ms 262144 KB 
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#include "bits_stdc++.h"
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define input(x) scanf("%lld", &x);
#define input2(x, y) scanf("%lld%lld", &x, &y);
#define input3(x, y, z) scanf("%lld%lld%lld", &x, &y, &z);
#define input4(x, y, z, a) scanf("%lld%lld%lld%lld", &x, &y, &z, &a);
#define print(x, y) printf("%lld%c", x, y);
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
#define discretize(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());
using namespace std;
//using namespace __gnu_pbds;
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>
typedef long long ll;
typedef long double ld;
typedef pair<ld, ll> pd;
typedef pair<string, ll> psl;
typedef pair<ll, ll> pi;
typedef pair<ll, pi> pii;
ll const MAXN = 3e5+5;
ll n, m, x;
vector<pi> edges;
bool mst[MAXN];
vector<pi> adj[MAXN];
vector<ll> cost;
// LCA
int lg(unsigned long long i) {
    return i ? __builtin_clzll(1) - __builtin_clzll(i) : -1;
}
ll label;
ll k, maxr;
vector<vector<pi > >rmq;
ll fa[MAXN],depth[MAXN], par[MAXN], ppath[MAXN];
vector<pi> arr;

void dfs(ll p, ll node) // euler path
{
	label++;
	fa[node] = label;
	arr.pb(mp(depth[node], node));
	for (pi u: adj[node])
	{
		if (u.f==p) continue;
		par[u.f] = node;
		ppath[u.f] = u.s;
		depth[u.f] = depth[node]+1;
		dfs(node, u.f);
		label++;
		arr.pb(mp(depth[node], node));
	}

}

void initrmq()
{
	maxr = arr.size();
	k = lg(maxr);
	rmq.assign(k+5, vector<pi> (maxr));
	rmq[0] = arr;
	for (ll i=1; i<=k; ++i)
	{
		for (ll j=0; j+ (1<<i) < maxr; ++j)
		{
			if (rmq[i-1][j].f < rmq[i-1][j + (1 << (i - 1))].f)
			{
				rmq[i][j] = rmq[i-1][j];
			}
			else
			{
				rmq[i][j] = rmq[i-1][j + (1 << (i - 1))];
			}
			
		}
	}
}

ll lca(ll node1, ll node2)
{
	ll l = fa[node1], r = fa[node2];
	if (l>r) swap(l,r);
	ll i = lg(r-l+1);
	if (rmq[i][l] < rmq[i][r - (1 << i) + 1])
	{
		return rmq[i][l].s;
	}
	else
	{
		return rmq[i][r - (1 << i) + 1].s;
	}
}

// UFDS
vector<ll> link1;
ll find(ll x)
{
	if (link1[x]!=x) link1[x] = find(link1[x]);
	return link1[x];
}
void unite(ll x, ll y)
{
	x = find(x), y = find(y);
	if (depth[x]>depth[y]) swap(x,y);
	link1[y] = link1[x];
}
// general
vector<ll> tobeset;
void update(ll from, ll until)
{
	from = find(from), until = find(until);
	ll counter = 0;
	while (from!=until)
	{
		counter++;
		tobeset.pb(ppath[from]);
		unite(from, par[from]);
		from = find(from), until = find(until);
		assert(counter<=3e5+5);
	}
}
int main()
{
	input2(n, m);
	link1.resize(n);
	edges.resize(m);
	cost.assign(m, -1);
	for (ll i=0; i<m; ++i) {input2(edges[i].f, edges[i].s); mst[i] = false; edges[i].f--; edges[i].s--;}
	for (ll i=0; i<n-1; ++i) 
	{
	    input(x); 
		x--;
		mst[x] = true;
		adj[edges[x].f].pb(mp(edges[x].s, x));
		adj[edges[x].s].pb(mp(edges[x].f, x));
	}
	label = -1;
	depth[0] = 0;
	dfs(-1, 0);
	initrmq();
	for (ll i=0; i<n; ++i) link1[i] = i;
	label = 0;
	for (ll i=0; i<m; ++i)
	{
		if (cost[i]!=-1) continue;
		if (mst[i]) {cost[i] = ++label; unite(edges[i].f, edges[i].s); continue;}
		ll lcanow = lca(edges[i].f, edges[i].s);
		tobeset.resize(0);
		update(edges[i].f, lcanow);
		update(edges[i].s, lcanow);
		sort(tobeset.begin(), tobeset.end());
		for (ll j=0; j<tobeset.size(); ++j) {cost[tobeset[j]] = ++label;}
		cost[i] = ++label;
	}
	for (ll i=0; i<m; ++i) print(cost[i], ' ');
	
	
	
	return 0;
}

Compilation message

riggedroads.cpp: In function 'int main()':
riggedroads.cpp:160:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  160 |   for (ll j=0; j<tobeset.size(); ++j) {cost[tobeset[j]] = ++label;}
      |                ~^~~~~~~~~~~~~~~
riggedroads.cpp:12:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 | #define input2(x, y) scanf("%lld%lld", &x, &y);
      |                      ~~~~~^~~~~~~~~~~~~~~~~~~~
riggedroads.cpp:132:2: note: in expansion of macro 'input2'
  132 |  input2(n, m);
      |  ^~~~~~
riggedroads.cpp:12:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 | #define input2(x, y) scanf("%lld%lld", &x, &y);
      |                      ~~~~~^~~~~~~~~~~~~~~~~~~~
riggedroads.cpp:136:26: note: in expansion of macro 'input2'
  136 |  for (ll i=0; i<m; ++i) {input2(edges[i].f, edges[i].s); mst[i] = false; edges[i].f--; edges[i].s--;}
      |                          ^~~~~~
riggedroads.cpp:11:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 | #define input(x) scanf("%lld", &x);
      |                  ~~~~~^~~~~~~~~~~~
riggedroads.cpp:139:6: note: in expansion of macro 'input'
  139 |      input(x);
      |      ^~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14684 KB Output is correct
2 Correct 4 ms 14680 KB Output is correct
3 Correct 3 ms 14684 KB Output is correct

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14684 KB Output is correct
2 Correct 4 ms 14680 KB Output is correct
3 Correct 3 ms 14684 KB Output is correct
4 Correct 5 ms 15196 KB Output is correct
5 Correct 4 ms 15196 KB Output is correct
6 Correct 3 ms 15192 KB Output is correct
7 Correct 4 ms 15104 KB Output is correct
8 Correct 3 ms 15196 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 98360 KB Output is correct
2 Correct 115 ms 123680 KB Output is correct
3 Correct 80 ms 37992 KB Output is correct
4 Correct 221 ms 262144 KB Output is correct
5 Runtime error 151 ms 262144 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 116236 KB Output is correct
2 Correct 69 ms 50900 KB Output is correct
3 Correct 31 ms 32464 KB Output is correct
4 Correct 81 ms 89296 KB Output is correct
5 Correct 31 ms 45264 KB Output is correct

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 244 ms 241084 KB Output is correct
2 Runtime error 217 ms 262144 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #6
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 166076 KB Output is correct
2 Correct 110 ms 115644 KB Output is correct
3 Runtime error 319 ms 262144 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #7
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14684 KB Output is correct
2 Correct 4 ms 14680 KB Output is correct
3 Correct 3 ms 14684 KB Output is correct
4 Correct 5 ms 15196 KB Output is correct
5 Correct 4 ms 15196 KB Output is correct
6 Correct 3 ms 15192 KB Output is correct
7 Correct 4 ms 15104 KB Output is correct
8 Correct 3 ms 15196 KB Output is correct
9 Correct 76 ms 98360 KB Output is correct
10 Correct 115 ms 123680 KB Output is correct
11 Correct 80 ms 37992 KB Output is correct
12 Correct 221 ms 262144 KB Output is correct
13 Runtime error 151 ms 262144 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -