QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#688545#7860. Graph of Maximum Degree 3kierankihnWA 168ms50360kbC++178.3kb2024-10-30 10:46:522024-10-30 10:46:53

Judging History

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

  • [2024-10-30 10:46:53]
  • 评测
  • 测评结果:WA
  • 用时:168ms
  • 内存:50360kb
  • [2024-10-30 10:46:52]
  • 提交

answer

#include <bits/stdc++.h>

namespace solution
{
    // clang-format off
    typedef bool bol;typedef char chr;typedef double dbi;typedef long long i64;typedef __int128 i128;constexpr dbi EPS=1e-8;constexpr int MOD=998244353;template<typename T>T qpow(T a,i64 b=MOD-2,i64 c=MOD){T res=1;while(b){if(b&1){res*=a,res%=c;}a*=a,a%=c,b>>=1;}return res;}template<typename T>T&cmax(T&x,const T y){return x>=y?x:x=y;}template<typename T>T&cmin(T&x,const T y){return x<=y?x:x=y;}template<typename T>T abs(T x){return x>=0?x:-x;}i64 floor(dbi x){return x+EPS;}i64 ceil(dbi x){return x-EPS+1;}template<typename T1,typename T2>struct pair{T1 fi;T2 se;bol operator==(const pair&a)const{return fi==a.fi&&se==a.se;}bol operator!=(const pair&a)const{return fi!=a.fi||se!=a.se;}bol operator<(const pair&a)const{return fi!=a.fi?fi<a.fi:se<a.se;}bol operator<=(const pair&a)const{return fi!=a.fi?fi<=a.fi:se<=a.se;}bol operator>(const pair&a)const{return fi!=a.fi?fi>a.fi:se>a.se;}bol operator>=(const pair&a)const{return fi!=a.fi?fi>=a.fi:se>=a.se;}};typedef pair<int,int>pii;template<i64 MOD=MOD>class ModInt{public:i64 val;ModInt<MOD>(i64 x=0):val(x>=0?(x<MOD?x:x%MOD):(x%MOD+MOD)){}ModInt operator+(const ModInt a)const{return ModInt(val+a.val>=MOD?val+a.val-MOD:val+a.val);}ModInt operator-(const ModInt a)const{return ModInt(val-a.val>=0?val-a.val:val-a.val+MOD);}ModInt operator*(const ModInt a)const{return ModInt(val*a.val%MOD);}ModInt operator/(const ModInt a)const{return ModInt(val*qpow(a,MOD-2).val%MOD);}ModInt operator&(const ModInt a)const{return ModInt(val&a.val);}ModInt operator|(const ModInt a)const{return ModInt((val|a.val)%MOD);}ModInt operator^(const ModInt a)const{return ModInt((val^a.val)%MOD);}ModInt operator<<(const ModInt a)const{return ModInt((val<<a.val)%MOD);}ModInt operator>>(const ModInt a)const{return ModInt(val>>a.val);}ModInt&operator++(){return val=val+1>=MOD?val+1-MOD:val+1,*this;}ModInt&operator+=(const ModInt a){return val=val+a.val>=MOD?val+a.val-MOD:val+a.val,*this;}ModInt&operator--(){return val=val-1>=0?val-1:val-1+MOD,*this;}ModInt&operator-=(const ModInt a){return val=val-a.val>=0?val-a.val:val-a.val+MOD,*this;}ModInt&operator*=(const ModInt a){return val=val*a.val%MOD,*this;}ModInt&operator/=(const ModInt a){return val=val*qpow(a,MOD-2).val%MOD,*this;}ModInt&operator&=(const ModInt a){return val=val&a.val,*this;}ModInt&operator|=(const ModInt a){return val=(val|a.val)%MOD,*this;}ModInt&operator^=(const ModInt a){return val=(val^a.val)%MOD,*this;}ModInt&operator<<=(const ModInt a){return val=(val<<a.val)%MOD,*this;}ModInt&operator>>=(const ModInt a){return val=val>>a.val,*this;}bol operator==(const ModInt&a)const{return val==a.val;}bol operator!=(const ModInt&a)const{return val!=a.val;}bol operator<(const ModInt&a)const{return val<a.val;}bol operator<=(const ModInt&a)const{return val<=a.val;}bol operator>(const ModInt&a)const{return val>a.val;}bol operator>=(const ModInt&a)const{return val>=a.val;}};template<i64 MOD=MOD>ModInt<MOD>qpow(ModInt<MOD>a,i64 b=MOD-2,i64 c=MOD){assert(c==MOD);ModInt<MOD>res=1;while(b){if(b&1){res*=a;}a*=a,b>>=1;}return res;}typedef ModInt<MOD>moi;class IO{public:i64 readi(){chr ch;i64 res=0,f=1;while(std::isdigit(ch=std::getchar())==false){f=(ch!='-');}do{res=res*10+(ch-'0');}while(std::isdigit(ch=std::getchar())==true);return res*(f?1:-1);}i128 readi128(){chr ch;i128 res=0,f=1;while(std::isdigit(ch=std::getchar())==false){f=(ch!='-');}do{res=res*10+(ch-'0');}while(std::isdigit(ch=std::getchar())==true);return res*(f?1:-1);}chr readc(){chr res=std::getchar();while(res==' '||res=='\n'){res=std::getchar();}return res;}std::string reads(){std::string res;std::cin>>res;return res;}template<typename T>T&read(T&x){return std::cin>>x,x;}int&read(int&x){return x=readi();}i64&read(i64&x){return x=readi();}i128&read(i128&x){return x=readi128();}template<i64 MOD=MOD>ModInt<MOD>&read(ModInt<MOD>&x){return x=readi();}chr&read(chr&x){return x=readc();}dbi&read(dbi&x){return scanf("%lf",&x),x;}template<typename T1,typename T2>pair<T1,T2>&read(pair<T1,T2>&x){return read(x.fi),read(x.se),x;}template<typename First,typename...Rest>void read(First&first,Rest&...rest){read(first);read(rest...);}template<typename T>void reada(T begin,T end){for(T iter=begin;iter!=end;iter++){read(*iter);}}void writei(i64 x){if(x<0){std::putchar('-'),writei(-x);return;}if(x>=10){writei(x/10);}std::putchar(x%10+'0');}void writei128(i128 x){if(x<0){std::putchar('-'),writei128(-x);return;}if(x>=10){writei128(x/10);}std::putchar(x%10+'0');}void writec(char x){std::putchar(x);}void writed(dbi x){printf("%lf",x);}template<typename T>void write(T x){std::cout<<x;}void write(int x){writei(x);}void write(i64 x){writei(x);}void write(i128 x){writei128(x);}template<i64 MOD=MOD>void write(ModInt<MOD>x){writei(x.val);}void write(char x){writec(x);}void write(dbi x){writed(x);}template<typename T1,typename T2>void write(pair<T1,T2>x){write(x.fi),std::putchar(' '),write(x.se);}template<typename First,typename...Rest>void write(First first,Rest...rest){write(first),std::putchar(' ');write(rest...);}template<typename First,typename...Rest>void writeln(First first,Rest...rest){write(first,rest...),std::putchar('\n');}template<typename T>void writea(T begin,T end){for(T iter=begin;iter!=end;iter++){write(*iter),std::putchar(' ');}}template<typename T>void writealn(T begin,T end){writea(begin,end),std::putchar('\n');}}io;
    // clang-format on

    constexpr int MAXN = 2e5 + 5;

    int n, m;

    int a[MAXN], b[MAXN], c[MAXN];

    int deg[2][MAXN];

    std::vector<int> e[2][MAXN];

    std::set<std::basic_string<int>> s[2];

    int vis[2][MAXN];
    std::deque<int> q;
    void dfs(int u, int color, int fa)
    {
        vis[color][u] = true;

        q.push_back(u);

        for (auto v : e[color][u])
        {
            if (v != fa)
            {
                for (int i = 1; i <= q.size() && i <= 3; i++)
                {
                    std::basic_string<int> x = {v};
                    for (int j = 1; j <= i; j++)
                    {
                        int flag = v != q[q.size() - j];
                        for (auto v_ : e[color][v])
                        {
                            if (v_ != u && v_ == q[q.size() - j])
                            {
                                flag = false;
                                break;
                            }
                        }

                        if (flag == false)
                        {
                            x.clear();
                            break;
                        }

                        x.push_back(q[q.size() - j]);
                    }

                    if (x.empty() == false)
                    {
                        std::sort(x.begin(), x.end());
                        s[color].insert(x);
                    }
                }

                if (vis[color][v] == false)
                {
                    dfs(v, color, u);
                }
            }
        }
    }

    int mian()
    {
        // std::freopen("graph.in", "r", stdin);
        // std::freopen("graph.out", "w", stdout);

        io.read(n, m);
        for (int i = 1; i <= m; i++)
        {
            int u = io.readi(), v = io.readi(), w = io.readi();

            deg[w][a[i] = u]++, deg[w][b[i] = v]++, c[i] = w;
        }

        for (int i = 1; i <= m; i++)
        {
            if (deg[c[i]][a[i]] <= 2 && deg[c[i]][b[i]] <= 2)
            {
                e[c[i]][a[i]].push_back(b[i]), e[c[i]][b[i]].push_back(a[i]);
            }
        }

        for (int i = 1; i <= n; i++)
        {
            for (int j = 0; j <= 1; j++)
            {
                if (deg[j][i] == 1 && vis[j][i] == false)
                {
                    dfs(i, j, 0), q.clear();
                }
            }
        }

        for (int i = 1; i <= n; i++)
        {
            for (int j = 0; j <= 1; j++)
            {
                if (deg[j][i] == 2 && vis[j][i] == false)
                {
                    dfs(i, j, 0), q.clear();
                }
            }
        }

        int ans = n;
        for (auto i : s[0])
        {
            if (s[1].find(i) != s[1].end())
            {
                ans++;
            }
        }

        io.writeln(ans);

        return 0;
    }
} // namespace solution

int main()
{
    solution::mian();
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 15836kb

input:

3 4
1 2 0
1 3 1
2 3 0
2 3 1

output:

5

result:

ok 1 number(s): "5"

Test #2:

score: 0
Accepted
time: 2ms
memory: 17832kb

input:

4 6
1 2 0
2 3 0
3 4 0
1 4 1
2 4 1
1 3 1

output:

5

result:

ok 1 number(s): "5"

Test #3:

score: 0
Accepted
time: 0ms
memory: 16276kb

input:

20 28
9 6 1
9 6 0
3 8 0
8 4 0
3 8 1
3 4 1
2 13 0
13 1 0
19 1 0
2 1 1
2 19 1
13 19 1
14 15 1
14 15 0
7 12 0
12 17 0
20 17 0
7 17 1
7 20 1
12 20 1
16 18 0
18 10 0
5 10 0
16 10 1
16 5 1
18 5 1
4 6 0
9 11 0

output:

27

result:

ok 1 number(s): "27"

Test #4:

score: 0
Accepted
time: 0ms
memory: 15924kb

input:

100 150
93 23 0
23 81 0
76 81 0
93 81 1
93 76 1
23 76 1
100 65 0
65 56 0
19 56 0
100 56 1
100 19 1
65 19 1
2 98 0
2 98 1
26 63 0
63 90 0
26 63 1
26 90 1
6 11 0
11 67 0
6 11 1
6 67 1
37 89 0
89 64 0
25 64 0
37 64 1
37 25 1
89 25 1
84 10 0
10 29 0
75 29 0
84 29 1
84 75 1
10 75 1
7 70 1
7 70 0
28 92 0
...

output:

141

result:

ok 1 number(s): "141"

Test #5:

score: 0
Accepted
time: 113ms
memory: 41988kb

input:

100000 133680
36843 86625 0
86625 63051 0
35524 63051 0
36843 63051 1
36843 35524 1
86625 35524 1
55797 82715 0
55797 82715 1
70147 35104 0
35104 91732 0
70147 35104 1
70147 91732 1
94917 70395 0
70395 68250 0
24100 68250 0
94917 68250 1
94917 24100 1
70395 24100 1
83033 18450 1
83033 18450 0
34462 ...

output:

144604

result:

ok 1 number(s): "144604"

Test #6:

score: 0
Accepted
time: 110ms
memory: 41980kb

input:

100000 133388
86620 74346 0
74346 19047 0
54911 19047 0
86620 19047 1
86620 54911 1
74346 54911 1
23715 93094 0
93094 91208 0
63189 91208 0
23715 91208 1
23715 63189 1
93094 63189 1
99337 41426 1
99337 41426 0
83742 45546 0
45546 73862 0
83742 45546 1
83742 73862 1
85256 2812 0
2812 59368 0
85918 59...

output:

144348

result:

ok 1 number(s): "144348"

Test #7:

score: 0
Accepted
time: 161ms
memory: 50360kb

input:

100000 150000
86541 24385 0
24385 75745 0
52353 75745 0
86541 75745 1
86541 52353 1
24385 52353 1
89075 78015 0
89075 78015 1
52519 74846 0
74846 12045 0
73265 12045 0
52519 12045 1
52519 73265 1
74846 73265 1
17884 63159 0
63159 47308 0
56073 47308 0
17884 47308 1
17884 56073 1
63159 56073 1
72134 ...

output:

144639

result:

ok 1 number(s): "144639"

Test #8:

score: 0
Accepted
time: 157ms
memory: 50096kb

input:

100000 150000
91951 68612 1
91951 68612 0
18361 92673 0
92673 52678 0
86520 52678 0
18361 52678 1
18361 86520 1
92673 86520 1
58779 2421 0
58779 2421 1
66622 6461 0
6461 96943 0
66622 6461 1
66622 96943 1
27201 480 1
27201 480 0
19082 3895 0
3895 17796 0
3117 17796 0
19082 17796 1
19082 3117 1
3895 ...

output:

144471

result:

ok 1 number(s): "144471"

Test #9:

score: 0
Accepted
time: 155ms
memory: 50168kb

input:

100000 150000
43756 3552 0
3552 90269 0
43756 3552 1
43756 90269 1
11104 36935 1
11104 36935 0
11648 5480 0
5480 45320 0
11648 5480 1
11648 45320 1
19216 85746 0
19216 85746 1
68825 11173 0
11173 43155 0
68825 11173 1
68825 43155 1
27349 75259 0
27349 75259 1
1704 24478 0
24478 5980 0
1704 24478 1
1...

output:

144217

result:

ok 1 number(s): "144217"

Test #10:

score: 0
Accepted
time: 159ms
memory: 50184kb

input:

99999 149998
51151 43399 0
51151 43399 1
45978 28343 0
28343 9008 0
85724 9008 0
45978 9008 1
45978 85724 1
28343 85724 1
79446 12915 0
12915 65925 0
28869 65925 0
79446 65925 1
79446 28869 1
12915 28869 1
82642 95556 0
95556 68817 0
68334 68817 0
82642 68817 1
82642 68334 1
95556 68334 1
61212 7638...

output:

144219

result:

ok 1 number(s): "144219"

Test #11:

score: 0
Accepted
time: 168ms
memory: 49980kb

input:

100000 149999
26736 28785 0
28785 37945 0
26736 28785 1
26736 37945 1
1240 74368 0
74368 45022 0
1240 74368 1
1240 45022 1
40673 1276 0
1276 56395 0
40673 1276 1
40673 56395 1
35181 63341 0
63341 35131 0
60120 35131 0
35181 35131 1
35181 60120 1
63341 60120 1
99363 36973 0
99363 36973 1
85717 77683 ...

output:

144380

result:

ok 1 number(s): "144380"

Test #12:

score: 0
Accepted
time: 158ms
memory: 49732kb

input:

100000 150000
63695 11044 0
11044 34978 0
56531 34978 0
63695 34978 1
63695 56531 1
11044 56531 1
72139 3715 0
3715 21024 0
96696 21024 0
72139 21024 1
72139 96696 1
3715 96696 1
54670 49014 0
54670 49014 1
7670 61055 0
61055 38409 0
7670 61055 1
7670 38409 1
83399 50676 0
50676 98893 0
60069 98893 ...

output:

144559

result:

ok 1 number(s): "144559"

Test #13:

score: 0
Accepted
time: 0ms
memory: 15900kb

input:

1 0

output:

1

result:

ok 1 number(s): "1"

Test #14:

score: 0
Accepted
time: 2ms
memory: 13968kb

input:

100000 0

output:

100000

result:

ok 1 number(s): "100000"

Test #15:

score: 0
Accepted
time: 146ms
memory: 49584kb

input:

100000 150000
95066 31960 0
31960 89758 0
10935 89758 0
95066 89758 1
95066 10935 1
31960 10935 1
48016 97823 0
97823 10871 0
23454 10871 0
48016 10871 1
48016 23454 1
97823 23454 1
73749 35525 0
35525 54232 0
42182 54232 0
73749 54232 1
73749 42182 1
35525 42182 1
75405 71341 0
71341 70032 0
3284 7...

output:

125000

result:

ok 1 number(s): "125000"

Test #16:

score: 0
Accepted
time: 0ms
memory: 17948kb

input:

4 6
1 2 0
1 2 1
1 3 0
2 4 1
3 4 0
3 4 1

output:

7

result:

ok 1 number(s): "7"

Test #17:

score: -100
Wrong Answer
time: 57ms
memory: 33532kb

input:

99998 115940
40840 40839 0
28249 28248 0
24785 24783 0
36536 36534 1
71904 71901 1
62023 62021 0
34737 34740 1
18430 18434 0
27506 27505 1
4665 4664 1
36578 36577 1
99311 99314 1
43484 43482 0
26457 26459 1
99698 99695 0
10170 10172 1
98176 98179 1
47786 47785 1
56529 56531 1
86896 86895 1
78204 782...

output:

104943

result:

wrong answer 1st numbers differ - expected: '104913', found: '104943'