QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#93683#5522. F*** 3-Colorable GraphsCUET_infinite_tsukuyomi#WA 9ms4660kbC++142.4kb2023-04-02 04:22:402023-04-02 04:22:44

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-02 04:22:44]
  • 评测
  • 测评结果:WA
  • 用时:9ms
  • 内存:4660kb
  • [2023-04-02 04:22:40]
  • 提交

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[20005];
int vis[200005];
int dfs(int pos, int pre) {
    // cout << pos << pre << endl;
    if(vis[pos]) return 1;
    vis[pos] = 1;
    for(auto it : v[pos]) {
        if(it == pre) continue;
        if(dfs(it, pos)) 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);
    }
    int cyc = dfs(1, 1);
    if(cyc) cout << 2 << endl;
    else cout << 3 << endl;
}
int main()
{
    boost_;
    int t = 1;
    // cin >> t;
    for(int i=1;i<=t;i++)
    {
        // cout<<"Case "<<i<<":";
       solve();
    }
}

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 3900kb

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: 1ms
memory: 4044kb

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
Wrong Answer
time: 9ms
memory: 4660kb

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:

2

result:

wrong answer 1st numbers differ - expected: '3', found: '2'