Submission #877337

#	Time	Username	Problem	Language	Result	Execution time	Memory
877337		Boycl07	Rigged Roads (NOI19_riggedroads)	C++17	100 / 100	197 ms	42664 KiB

riggedroads

#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 (stderr)

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 / 8
• Subtask 2: 19 / 19
• Subtask 3: 9 / 9
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 12 / 12
• Subtask 7: 32 / 32