oj.uz

답안 #930036

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
930036 2024-02-18T09:33:42 Z pan Rigged Roads (NOI19_riggedroads) C++17
37 / 100
 259 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);
	while (from!=until)
	{
		tobeset.pb(ppath[from]);
		unite(from, par[from]);
		from = find(from), until = find(until);
	}
}
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:157: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]
  157 |   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:129:2: note: in expansion of macro 'input2'
  129 |  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:133:26: note: in expansion of macro 'input2'
  133 |  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:136:6: note: in expansion of macro 'input'
  136 |      input(x);
      |      ^~~~~

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 14680 KB Output is correct
2 Correct 3 ms 14684 KB Output is correct
3 Correct 4 ms 14684 KB Output is correct

Subtask #2
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 14680 KB Output is correct
2 Correct 3 ms 14684 KB Output is correct
3 Correct 4 ms 14684 KB Output is correct
4 Correct 3 ms 15196 KB Output is correct
5 Correct 3 ms 15196 KB Output is correct
6 Correct 4 ms 15196 KB Output is correct
7 Correct 3 ms 14940 KB Output is correct
8 Correct 3 ms 15284 KB Output is correct

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 79 ms 99644 KB Output is correct
2 Correct 114 ms 126204 KB Output is correct
3 Correct 79 ms 40892 KB Output is correct
4 Runtime error 168 ms 262144 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 104 ms 117824 KB Output is correct
2 Correct 69 ms 52532 KB Output is correct
3 Correct 31 ms 32980 KB Output is correct
4 Correct 85 ms 91264 KB Output is correct
5 Correct 36 ms 46020 KB Output is correct

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 233 ms 245688 KB Output is correct
2 Runtime error 210 ms 262144 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #6
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 176 ms 168740 KB Output is correct
2 Correct 107 ms 117436 KB Output is correct
3 Runtime error 259 ms 262144 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #7
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 14680 KB Output is correct
2 Correct 3 ms 14684 KB Output is correct
3 Correct 4 ms 14684 KB Output is correct
4 Correct 3 ms 15196 KB Output is correct
5 Correct 3 ms 15196 KB Output is correct
6 Correct 4 ms 15196 KB Output is correct
7 Correct 3 ms 14940 KB Output is correct
8 Correct 3 ms 15284 KB Output is correct
9 Correct 79 ms 99644 KB Output is correct
10 Correct 114 ms 126204 KB Output is correct
11 Correct 79 ms 40892 KB Output is correct
12 Runtime error 168 ms 262144 KB Execution killed with signal 9
13 Halted 0 ms 0 KB -