oj.uz

Submission #877337

# Submission time Handle Problem Language Result Execution time Memory
877337 2023-11-23T06:54:30 Z Boycl07 Rigged Roads (NOI19_riggedroads) C++17
100 / 100
 197 ms 42664 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
#define rep(i, n) for(int i = 1; i <= n; ++i)
#define forn(i, l, r) for(int i = l; i <= r; ++i)
#define ford(i, r, l) for(int i = r; i >= l; --i)
#define FOR(i, n) for(int i = 0; i < n; ++i)
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define task "MEETING"
#define endl "\n"
#define sz(a) int(a.size())
#define C(x, y) make_pair(x, y)
#define all(a) (a).begin(), (a).end()
#define bit(i, mask) (mask >> i & 1)
//#define int ll
 
template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
 
 inline int readInt()       {char c;while(c=getchar(),c!='-'&&(c<'0'||c>'9'));bool sign=(c=='-');if(sign)c=getchar();int n=c-'0';while(c=getchar(),c>='0'&&c<='9')n=10*n+c-'0';return(!sign)?n:-n;}
inline ll readLong()       {char c;while(c=getchar(),c!='-'&&(c<'0'||c>'9'));bool sign=(c=='-');if(sign)c=getchar();ll  n=c-'0';while(c=getchar(),c>='0'&&c<='9')n=10*n+c-'0';return(!sign)?n:-n;}
inline string readString() {char c;while(c=getchar(),c==' '||c=='\n'||c=='\t');string s({c});while(c=getchar(),c!=EOF&&c!=' '&&c!='\n'&&c!='\t')s+=c;return s;}
 
 
const int N =  3e5 + 10;
const int K = 1500 + 10;
const int M = 255 + 3;
const int N1 = 2e3 + 10;
const int MOD = 1e9 + 7;
const int INF = 1e9 + 1;
const ll LINF = 1e17 + 2;
const int block_size = 230;
const int LOG = 13;
const int offset = N;
const int LIM = 2e5;
const int AL = 26;

int n, m;

int d[N];

vector<pii> g[N];

int tin[N], tout[N], timedfs = 0, del[N], idx_edge[N], res[N], nx[N];
int node_idx[N];

pii a[N];

int find_nx(int u)
{
	return !del[nx[u]] ? nx[u] : nx[u] = find_nx(nx[u]);
}

void dfs(int u, int p, int id)
{
	tin[u] = ++timedfs;

	idx_edge[u] = id;
	node_idx[id] = u;
	nx[u] = p;

	for(auto &[v, id] : g[u]) if(v != p) dfs(v, u, id);

	tout[u] = ++timedfs;
}

bool is_anc(int u, int v)
{
	return tin[u] <= tin[v] && tout[v] <= tout[u];
}

void solve()
{
    cin >> n >> m;
	rep(i, m)
	{
		cin >> a[i].fi >> a[i].se;
		res[i] = -1;
	}

	rep(i, n - 1)
	{
		int x;
		cin >> x;
		d[x] = 1;
		g[a[x].fi].pb({a[x].se, x});
		g[a[x].se].pb({a[x].fi, x});
	}

	dfs(1, 1, 0);

	int idx = 0;

	rep(i, m)
	{
		if(res[i] != -1) continue;
		if(d[i])
		{
			res[i] = ++idx;
			del[node_idx[i]] = 1;
			continue;
		}
		int u = a[i].fi, v = a[i].se;
		vector<int> edges;

		for(int x = del[u] ? find_nx(u) : u; !is_anc(x, v); x = find_nx(x))
			edges.pb(idx_edge[x]), del[x] = 1;
		
		for(int x = del[v] ? find_nx(v) : v; !is_anc(x, u); x = find_nx(x))
			edges.pb(idx_edge[x]), del[x] = 1;
		sort(all(edges));
		
		for(int x : edges) res[x] = ++idx;
		res[i] = ++idx;
	}
	rep(i, m) cout << res[i] << " ";
}
 
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
 
    if(fopen("ZONING.inp", "r"))
    {
        freopen("ZONING.inp", "r", stdin);
        freopen("ZONING.out", "w", stdout);
    }
 
    int TC = 1;
 
    while(TC--)
    {
        solve();
    }
 
    return 0;
}

Compilation message

riggedroads.cpp: In function 'int main()':
riggedroads.cpp:133:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  133 |         freopen("ZONING.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
riggedroads.cpp:134:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  134 |         freopen("ZONING.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14684 KB Output is correct
2 Correct 2 ms 14684 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 2 ms 14684 KB Output is correct
3 Correct 3 ms 14684 KB Output is correct
4 Correct 3 ms 14684 KB Output is correct
5 Correct 3 ms 14684 KB Output is correct
6 Correct 3 ms 14684 KB Output is correct
7 Correct 3 ms 14684 KB Output is correct
8 Correct 3 ms 14684 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 22224 KB Output is correct
2 Correct 54 ms 26056 KB Output is correct
3 Correct 54 ms 22264 KB Output is correct
4 Correct 89 ms 36800 KB Output is correct
5 Correct 94 ms 37084 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 27136 KB Output is correct
2 Correct 34 ms 22440 KB Output is correct
3 Correct 19 ms 19792 KB Output is correct
4 Correct 41 ms 25788 KB Output is correct
5 Correct 16 ms 20572 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 35600 KB Output is correct
2 Correct 137 ms 42416 KB Output is correct
3 Correct 31 ms 24048 KB Output is correct
4 Correct 46 ms 27628 KB Output is correct
5 Correct 158 ms 42664 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 30664 KB Output is correct
2 Correct 48 ms 27984 KB Output is correct
3 Correct 182 ms 39928 KB Output is correct
4 Correct 193 ms 38508 KB Output is correct
5 Correct 13 ms 18776 KB Output is correct

Subtask #7
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14684 KB Output is correct
2 Correct 2 ms 14684 KB Output is correct
3 Correct 3 ms 14684 KB Output is correct
4 Correct 3 ms 14684 KB Output is correct
5 Correct 3 ms 14684 KB Output is correct
6 Correct 3 ms 14684 KB Output is correct
7 Correct 3 ms 14684 KB Output is correct
8 Correct 3 ms 14684 KB Output is correct
9 Correct 30 ms 22224 KB Output is correct
10 Correct 54 ms 26056 KB Output is correct
11 Correct 54 ms 22264 KB Output is correct
12 Correct 89 ms 36800 KB Output is correct
13 Correct 94 ms 37084 KB Output is correct
14 Correct 55 ms 27136 KB Output is correct
15 Correct 34 ms 22440 KB Output is correct
16 Correct 19 ms 19792 KB Output is correct
17 Correct 41 ms 25788 KB Output is correct
18 Correct 16 ms 20572 KB Output is correct
19 Correct 126 ms 35600 KB Output is correct
20 Correct 137 ms 42416 KB Output is correct
21 Correct 31 ms 24048 KB Output is correct
22 Correct 46 ms 27628 KB Output is correct
23 Correct 158 ms 42664 KB Output is correct
24 Correct 98 ms 30664 KB Output is correct
25 Correct 48 ms 27984 KB Output is correct
26 Correct 182 ms 39928 KB Output is correct
27 Correct 193 ms 38508 KB Output is correct
28 Correct 13 ms 18776 KB Output is correct
29 Correct 172 ms 38584 KB Output is correct
30 Correct 197 ms 38272 KB Output is correct
31 Correct 165 ms 36404 KB Output is correct
32 Correct 55 ms 22380 KB Output is correct
33 Correct 177 ms 37056 KB Output is correct