oj.uz

Submission #877256

# Submission time Handle Problem Language Result Execution time Memory
877256 2023-11-23T05:01:28 Z nnhzzz Rigged Roads (NOI19_riggedroads) C++14
100 / 100
 265 ms 74408 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(long long int, long long int, long long int, long long 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 66 ms 16988 KB Output is correct
2 Correct 71 ms 16988 KB Output is correct
3 Correct 62 ms 16988 KB Output is correct

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 16988 KB Output is correct
2 Correct 71 ms 16988 KB Output is correct
3 Correct 62 ms 16988 KB Output is correct
4 Correct 5 ms 25176 KB Output is correct
5 Correct 5 ms 25180 KB Output is correct
6 Correct 5 ms 25180 KB Output is correct
7 Correct 6 ms 25180 KB Output is correct
8 Correct 5 ms 25224 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 38380 KB Output is correct
2 Correct 65 ms 47272 KB Output is correct
3 Correct 61 ms 42188 KB Output is correct
4 Correct 109 ms 71344 KB Output is correct
5 Correct 117 ms 69552 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 47396 KB Output is correct
2 Correct 38 ms 36028 KB Output is correct
3 Correct 22 ms 30616 KB Output is correct
4 Correct 46 ms 39868 KB Output is correct
5 Correct 21 ms 30676 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 47300 KB Output is correct
2 Correct 163 ms 49336 KB Output is correct
3 Correct 35 ms 27608 KB Output is correct
4 Correct 52 ms 30772 KB Output is correct
5 Correct 200 ms 58004 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 56760 KB Output is correct
2 Correct 82 ms 44584 KB Output is correct
3 Correct 265 ms 74408 KB Output is correct
4 Correct 209 ms 69812 KB Output is correct
5 Correct 17 ms 28116 KB Output is correct

Subtask #7
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 16988 KB Output is correct
2 Correct 71 ms 16988 KB Output is correct
3 Correct 62 ms 16988 KB Output is correct
4 Correct 5 ms 25176 KB Output is correct
5 Correct 5 ms 25180 KB Output is correct
6 Correct 5 ms 25180 KB Output is correct
7 Correct 6 ms 25180 KB Output is correct
8 Correct 5 ms 25224 KB Output is correct
9 Correct 45 ms 38380 KB Output is correct
10 Correct 65 ms 47272 KB Output is correct
11 Correct 61 ms 42188 KB Output is correct
12 Correct 109 ms 71344 KB Output is correct
13 Correct 117 ms 69552 KB Output is correct
14 Correct 72 ms 47396 KB Output is correct
15 Correct 38 ms 36028 KB Output is correct
16 Correct 22 ms 30616 KB Output is correct
17 Correct 46 ms 39868 KB Output is correct
18 Correct 21 ms 30676 KB Output is correct
19 Correct 159 ms 47300 KB Output is correct
20 Correct 163 ms 49336 KB Output is correct
21 Correct 35 ms 27608 KB Output is correct
22 Correct 52 ms 30772 KB Output is correct
23 Correct 200 ms 58004 KB Output is correct
24 Correct 146 ms 56760 KB Output is correct
25 Correct 82 ms 44584 KB Output is correct
26 Correct 265 ms 74408 KB Output is correct
27 Correct 209 ms 69812 KB Output is correct
28 Correct 17 ms 28116 KB Output is correct
29 Correct 229 ms 74040 KB Output is correct
30 Correct 261 ms 73224 KB Output is correct
31 Correct 221 ms 69808 KB Output is correct
32 Correct 64 ms 41300 KB Output is correct
33 Correct 219 ms 69296 KB Output is correct