QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#93711 | #5522. F*** 3-Colorable Graphs | CUET_infinite_tsukuyomi# | TL | 3ms | 5604kb | C++14 | 2.7kb | 2023-04-02 05:30:02 | 2023-04-02 05:30:03 |
Judging History
answer
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
// typedefs...
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<ll, ll> pll;
typedef trie<string,null_type,trie_string_access_traits<>,pat_trie_tag,trie_prefix_search_node_update>pref_trie;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> oset;
// constants...
const double PI = acos(-1);
const ll mod = 1000000007; // 998244353
const int MXS = 2e5+5;
const ll MXI = 1e9+5;
const ll MXL = 1e18+5;
const ll INF = 1e9+5;
const ll INFLL = 1e18+5;
const ll EPS = 1e-9;
// defines...
#define MP make_pair
#define PB push_back
#define fi first
#define se second
#define ordered_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
#define boost_ ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
// functions...
ll gcd(ll a, ll b){ while (b){ a %= b; swap(a, b);} return a;}
ll lcm(ll a, ll b){ return (a/gcd(a, b)*b);}
ll ncr(ll a, ll b){ ll x = max(a-b, b), ans=1; for(ll K=a, L=1; K>=x+1; K--, L++){ ans = ans * K; ans /= L;} return ans;}
ll bigmod(ll a,ll b,ll mod){ if(b==0){ return 1;} ll tm=bigmod(a,b/2,mod); tm=(tm*tm)%mod; if(b%2==1) tm=(tm*a)%mod; return tm;}
ll egcd(ll a,ll b,ll &x,ll &y){ if(a==0){ x=0; y=1; return b;} ll x1,y1; ll d=egcd(b%a,a,x1,y1); x=y1-(b/a)*x1; y=x1; return d;}
ll modpow(ll a,ll p,ll mod) {ll ans=1;while(p){if(p%2)ans=(ans*a)%mod;a=(a*a)%mod;p/=2;} return ans;}
ll inverse_mod(ll n,ll mod) {return modpow(n,mod-2,mod);}
vector<int> v[40005];
int vis[400005];
int dfs(int pos, int pre, int dis) {
// cout << pos << pre << endl;
vis[pos] = dis;
for(auto it : v[pos]) {
if(it == pre) continue;
if(vis[it]) {
if(vis[pos] - vis[it] + 1 == 4) return 1;
continue;
}
if(dfs(it, pos, dis + 1)) return 1;
}
return 0;
}
void solve()
{
int n, m;
cin >> n >> m;
for(int i = 0; i < m; i++) {
int x, y;
cin >> x >> y;
v[x].PB(y);
v[y].PB(x);
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= 2 * n; j++)
vis[j] = 0;
int cyc = dfs(i, i, 1);
if(cyc) {
cout << 2 << endl;
return;
}
}
cout << 3 << endl;
}
int main()
{
boost_;
int t = 1;
// cin >> t;
for(int i=1;i<=t;i++)
{
// cout<<"Case "<<i<<":";
solve();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 4412kb
input:
2 4 1 3 1 4 2 3 2 4
output:
2
result:
ok 1 number(s): "2"
Test #2:
score: 0
Accepted
time: 3ms
memory: 5604kb
input:
3 5 1 4 2 4 2 5 3 5 3 6
output:
3
result:
ok 1 number(s): "3"
Test #3:
score: -100
Time Limit Exceeded
input:
10000 20000 4570 11730 8803 16440 4257 15381 4455 17636 5256 13543 2172 18421 7735 17847 8537 16010 6175 12263 1079 13410 335 15901 3272 16233 7435 11454 4469 13374 1564 13416 1264 13446 7484 14510 8193 12267 628 15585 1388 11398 5444 19958 2059 18140 8947 13188 6214 17707 7940 12253 6726 11508 1839...