oj.uz

Submission #877257

# Submission time Handle Problem Language Result Execution time Memory
877257 2023-11-23T05:02:31 Z nnhzzz Rigged Roads (NOI19_riggedroads) C++14
100 / 100
 263 ms 51604 KB 
// cre: Nguyen Ngoc Hung - Go Go VOI 2024 :>

#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <unordered_set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <cstring>
#include <unordered_map>
#include <cmath>
#include <array>
#include <cassert>
#include <random>
#include <chrono>

using namespace std;

#define        __nnhzzz__  signed main()
#define          BIT(i,j)  ((i>>j)&1LL)
#define           MASK(i)  (1LL<<i)
#define            ALL(x)  (x).begin(),(x).end()
#define             SZ(x)  (int)(x).size()
#define                PB  push_back
#define                fi  first
#define                se  second
#define                ll  long long
#define                ld  long double
#define                vi  vector<int>
#define               vvi  vector<vi>
#define              vvvi  vector<vvi>
#define               pii  pair<int,int>
#define              vpii  vector<pii>
#define             vvpii  vector<vpii>
#define REPDIS(i,be,en,j)  for(int i = (be); i<=(en); i+=j)
#define     REPD(i,be,en)  for(int i = (be); i>=(en); --i)
#define      REP(i,be,en)  for(int i = (be); i<=(en); ++i)
#define              endl  "\n"
// #define               int  ll

//------------------------------------------------------------------------------------------------//
int readInt(){
    char c;
    do{ c = getchar(); }while(c!='-' && !isdigit(c));
    bool neg = (c=='-');
    int res = neg?0:c-'0';
    while(isdigit(c=getchar())) res = (res<<3)+(res<<1)+(c-'0');
    return neg?-res:res;
}
//------------------------------------------------------------------------------------------------//
const int oo = 1e9,LOG = 20,MAXN = 5e5+7,N = 1e2+3;
const int MOD = 1e9+7,MOD1 = 1e9+207,MOD2 = 1e9+407,MOD3 = 998244353;
const ld EPS = 1e-9,PI = acos(-1);
//------------------------------------------------------------------------------------------------//
template<typename T1, typename T2> bool mini(T1 &a, T2 b){if(a>b){a=b;return true;}return false;}
template<typename T1, typename T2> bool maxi(T1 &a, T2 b){if(a<b){a=b;return true;}return false;}
template<typename T> T gcd(T a, T b) { while(b) { a %= b; swap(a,b); } return a; }
template<typename T> T lcm(T a, T b) { return a/gcd(a,b)*b; }
//------------------------------------------------------------------------------------------------//

/*
----------------------------------------------------------------
    END OF TEMPLATE
----------------------------------------------------------------
    Nguyen Ngoc Hung - nnhzzz
    Training for VOI24 gold medal
----------------------------------------------------------------
*/

struct DSU{
	vi par;
	int n;

	int find(int u){
		return u==par[u]?u:par[u]=find(par[u]);
	}

	bool same(int u, int v){
		return find(u)==find(v);
	}

	bool unite(int u, int v){
		u = find(u); v = find(v);
		if(u==v) return false;
		par[v] = u;
		return true;
	}

	DSU(int _n):n(_n){
		par.resize(n+3);
		iota(ALL(par),0);
	}
};

struct edge{
	int u,v,w,id;

	bool operator < (const edge &other) const {
		return w<other.w;
	}
};

int ok[MAXN],vis[MAXN],s[MAXN],h[MAXN],p[MAXN],pe[MAXN],t[MAXN];
vector<edge> edges;
vpii adj[MAXN];
vi now,nho;
int n,m;

int find(int u){
	return s[u]<0?u:s[u]=find(s[u]);
}

void unite(int u, int v){
	if(s[u]>s[v]) swap(u,v);
	if(u!=v){
		if(h[t[u]]>h[t[v]]) t[u] = t[v];
		s[u] += s[v];
		s[v] = u;
	}
}

void dfs(int u, int par, int dep, int e){
	h[u] = dep;
	p[u] = par;
	pe[u] = e;
	for(auto &[v,id]:adj[u]){
		if(v==par) continue;
		dfs(v,u,dep+1,id);
	}
}

void sub1(){
	vi perm(m),res(m); iota(ALL(perm),0); iota(ALL(res),n);
	do{
		vector<edge> now = edges;
		REP(i,0,m-1) now[i].w = perm[i]+1;
		sort(ALL(now));
		DSU dsu(n);
		int flag = 1;
		REP(i,0,m-1){
			if(dsu.unite(now[i].u,now[i].v)){
				if(ok[now[i].id]==0){
					flag = 0;
					break;
				}
			}
		}
		if(flag) mini(res,perm);
	}while(next_permutation(ALL(perm)));
	for(auto &i:res) cout << i+1 << " ";
}

void sub5(){
	int cnt = 0;
	vi res;
	REP(i,1,m){
		if(ok[i]==0){
			res.push_back(m);
			continue;
		}
		res.push_back(++cnt);
	}
	for(auto &i:res) cout << i << " ";
}

void sub7(){
	dfs(1,0,0,0);
	REP(i,1,n){
		s[i] = -1;
		t[i] = i;
	}
	vi res(m+1,0);
	int j = 1;
	REP(i,1,m){
		int u = find(edges[i-1].u),v = find(edges[i-1].v);
		if(ok[i]==1 && res[i]==0){
			res[i] = j++;
			unite(u,v);
		}
		if(res[i]!=0) continue;
		// edge i - not mst
		vi tmp;
		while(u!=v){
			if(h[t[u]]<h[t[v]]) swap(u,v);
			tmp.push_back(pe[t[u]]);
			unite(u,find(p[t[u]]));
			u = find(u); v = find(v);
		}
		sort(ALL(tmp));
		for(auto &x:tmp) res[x] = j++;
		res[i] = j++;
	}
	REP(i,1,m) cout << res[i] << " ";
}

/*
6 6
1 4
1 2
2 3
4 5
3 4
5 6
2 3 4 5 6
*/

void solve(){
	cin >> n >> m;
	int s5 = 1;
	REP(i,1,m){
		int u,v; cin >> u >> v;
		edges.push_back({u,v,0,i});
		if(u!=i || v!=i%n+1) s5 = 0;
	}
	REP(i,1,n-1){
		int x; cin >> x;
		ok[x] = 1;
		adj[edges[x-1].u].emplace_back(edges[x-1].v,x);
		adj[edges[x-1].v].emplace_back(edges[x-1].u,x);
	}
	sub7(); return ;
	if(n<=9 && m<=9){
		sub1();
		return ;
	}
	if(s5 && n==m){
		sub5();
		return ;
	}
	sub7();
}

__nnhzzz__{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    #define task "test"
    if(fopen(task".inp","r")){
        freopen(task".inp","r",stdin);
        freopen(task".out","w",stdout);
    }
    #define task1 "ZONING"
    if(fopen(task1".inp","r")){
        freopen(task1".inp","r",stdin);
        freopen(task1".out","w",stdout);
    }

    int test = 1;

    while(test--){
      solve();
    }
    cerr << "\nTime elapsed: " << 1000*clock()/CLOCKS_PER_SEC << "ms\n";
    return 0;
}

/**  /\_/\
 *  (= ._.)
 *  / >TL \>AC
**/

Compilation message

riggedroads.cpp: In function 'void dfs(int, int, int, int)':
riggedroads.cpp:153:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  153 |  for(auto &[v,id]:adj[u]){
      |            ^
riggedroads.cpp: In function 'int main()':
riggedroads.cpp:265:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  265 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
riggedroads.cpp:266:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  266 |         freopen(task".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
riggedroads.cpp:270:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  270 |         freopen(task1".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
riggedroads.cpp:271:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  271 |         freopen(task1".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

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

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 23132 KB Output is correct
2 Correct 4 ms 23132 KB Output is correct
3 Correct 4 ms 23128 KB Output is correct
4 Correct 4 ms 23128 KB Output is correct
5 Correct 4 ms 23132 KB Output is correct
6 Correct 4 ms 23132 KB Output is correct
7 Correct 4 ms 23132 KB Output is correct
8 Correct 4 ms 23132 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 29652 KB Output is correct
2 Correct 58 ms 33216 KB Output is correct
3 Correct 62 ms 32552 KB Output is correct
4 Correct 102 ms 43764 KB Output is correct
5 Correct 96 ms 44232 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 35520 KB Output is correct
2 Correct 43 ms 29124 KB Output is correct
3 Correct 21 ms 26348 KB Output is correct
4 Correct 41 ms 32456 KB Output is correct
5 Correct 18 ms 26576 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 45064 KB Output is correct
2 Correct 154 ms 49292 KB Output is correct
3 Correct 35 ms 30420 KB Output is correct
4 Correct 56 ms 33608 KB Output is correct
5 Correct 186 ms 51604 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 39360 KB Output is correct
2 Correct 59 ms 33852 KB Output is correct
3 Correct 211 ms 46372 KB Output is correct
4 Correct 174 ms 43980 KB Output is correct
5 Correct 16 ms 24796 KB Output is correct

Subtask #7
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 23132 KB Output is correct
2 Correct 4 ms 23132 KB Output is correct
3 Correct 4 ms 23128 KB Output is correct
4 Correct 4 ms 23128 KB Output is correct
5 Correct 4 ms 23132 KB Output is correct
6 Correct 4 ms 23132 KB Output is correct
7 Correct 4 ms 23132 KB Output is correct
8 Correct 4 ms 23132 KB Output is correct
9 Correct 37 ms 29652 KB Output is correct
10 Correct 58 ms 33216 KB Output is correct
11 Correct 62 ms 32552 KB Output is correct
12 Correct 102 ms 43764 KB Output is correct
13 Correct 96 ms 44232 KB Output is correct
14 Correct 55 ms 35520 KB Output is correct
15 Correct 43 ms 29124 KB Output is correct
16 Correct 21 ms 26348 KB Output is correct
17 Correct 41 ms 32456 KB Output is correct
18 Correct 18 ms 26576 KB Output is correct
19 Correct 161 ms 45064 KB Output is correct
20 Correct 154 ms 49292 KB Output is correct
21 Correct 35 ms 30420 KB Output is correct
22 Correct 56 ms 33608 KB Output is correct
23 Correct 186 ms 51604 KB Output is correct
24 Correct 140 ms 39360 KB Output is correct
25 Correct 59 ms 33852 KB Output is correct
26 Correct 211 ms 46372 KB Output is correct
27 Correct 174 ms 43980 KB Output is correct
28 Correct 16 ms 24796 KB Output is correct
29 Correct 232 ms 46268 KB Output is correct
30 Correct 247 ms 45064 KB Output is correct
31 Correct 263 ms 44120 KB Output is correct
32 Correct 62 ms 31004 KB Output is correct
33 Correct 236 ms 42636 KB Output is correct