QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#93875 | #5522. F*** 3-Colorable Graphs | Asad_Bin | TL | 758ms | 7020kb | C++17 | 3.0kb | 2023-04-03 15:04:16 | 2023-04-03 15:04:18 |
Judging History
answer
// . . . Bismillahir Rahmanir Rahim . . .
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#ifndef ONLINE_JUDGE
#define dbg_out cout
#define debug(...) dbg_out << "DBG )> "; __f(#__VA_ARGS__, __VA_ARGS__);
template<typename T1, typename T2> ostream& operator<<(ostream& out, pair<T1, T2> pr) { out << "{ " << pr.first << ", " << pr.second << " }"; return out; }
template<typename T1> ostream& operator<<(ostream& out, vector<T1> vec) { out << "{ "; for (auto &x: vec) out << x << ", "; out << "}"; return out; }
template<typename T1, size_t size> ostream& operator<<(ostream& out, array<T1, size> arr) { out << "{ "; for (auto &x: arr) out << x << ", "; out << "}"; return out; }
template<typename T1, typename T2> ostream& operator<<(ostream& out, map<T1, T2> mp) { out << "{ ";for (auto &x: mp) out << x.first << ": " << x.second << ", "; out << "}"; return out; }
template <typename Arg1> void __f(const char* name, Arg1&& arg1) { while (isspace(name[0])) name++; (isalpha(name[0]) || name[0] == '_') ? dbg_out << name << ": " << arg1 << "\n" : dbg_out << arg1 << "\n"; dbg_out.flush();}
template <typename Arg1, typename... Args> void __f (const char* names, Arg1&& arg1, Args&&... args) { const char *comma = strchr(names + 1, ','); while (isspace(names[0])) names++; (isalpha(names[0]) || names[0] == '_') ? dbg_out.write(names, comma - names) << ": " << arg1 << " | " : dbg_out << arg1 << " | "; __f(comma + 1, args...);}
#else
#define debug(...)
#endif
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);}
const int N = 1e4;
vector<int> ara[2*N+5];
bool dp[2*N+5][4];
bool calc(int at, int p, int x, int h)
{
if(h == 3){
//cout << at << ' ' << h << "\n";
for(int v : ara[at]){
if(x == v) return true;
}
return false;
}
//if(dp[at][h]) return 0;
dp[at][h] = 1;
//cout << at << ' ' << h << "\n";
//cout << at << ' ' << h << "\n";
bool ok = 0;
for(auto v : ara[at]){
if(v != p){
ok |= calc(v, at, x, h+1);
if(ok) return ok;
}
}
return 0;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
memset(dp, 0, sizeof dp);
int n, m; cin >> n >> m;
for(int K = 0; K < m; K++){
int a, b; cin >> a >> b;
ara[a].push_back(b);
ara[b].push_back(a);
}
bool ok = 0;
for(int K = 1; K <= n; K++){
ok |= calc(K, K, K, 0);
if(ok) break;
}
if(ok) cout << 2 << "\n";
else cout << 3 << "\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 4080kb
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: 2ms
memory: 3976kb
input:
3 5 1 4 2 4 2 5 3 5 3 6
output:
3
result:
ok 1 number(s): "3"
Test #3:
score: 0
Accepted
time: 10ms
memory: 4580kb
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...
output:
3
result:
ok 1 number(s): "3"
Test #4:
score: 0
Accepted
time: 758ms
memory: 7020kb
input:
9999 199986 8408 17344 1353 16706 3364 17274 9410 10006 9387 19375 9169 18239 3930 12759 4728 11328 5192 17935 7616 19485 3138 12714 8595 18490 6020 15039 9319 17097 7842 16814 7644 18723 2190 10117 3971 13350 232 15408 6984 12842 6988 17196 9744 18905 6759 13371 4115 18937 1842 13513 6245 18736 207...
output:
2
result:
ok 1 number(s): "2"
Test #5:
score: -100
Time Limit Exceeded
input:
9999 199986 1284 14140 5071 12232 7015 15577 4211 14089 3764 14645 4634 19044 1944 18455 5249 19603 1607 10182 9986 19929 1132 18778 3848 10147 636 10961 1994 14118 5084 18986 4067 19483 2288 17337 3108 15530 2258 12709 9809 14997 4860 11548 1779 13012 5062 16123 7418 10293 7726 11733 1145 14062 369...