QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#323014	#4829. Mark on a Graph	Goldenglow1427	AC ✓	0ms	1720kb	C++14	1.8kb	2024-02-08 06:18:00	2024-02-08 06:18:00

Judging History

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

[2024-02-08 06:18:00]
评测

测评结果：AC
用时：0ms
内存：1720kb

查看

[2024-02-08 06:18:00]
提交

answer

/*
ID: Victor Chen [mail_vi1]
PROG: Mark on a Graph
LANG: C++
*/

#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

const int Maxn = 1000;
const int Maxm = 5000;

int n, m;

class Graph
{
    public:
        int cnt, head[Maxn+10];
        struct Edge
        {
            int to, nxt;
        }p[2*Maxm+100];

        void AddEdge(int x, int y)
        {
            cnt++;
            p[cnt].to = y;

            p[cnt].nxt = head[x];
            head[x] = cnt;
        }

        bool is_connected(int x, int y)
        {
            for(int i=head[x]; i!=0; i=p[i].nxt)
                if(p[i].to == y)
                    return true;
            return false;
        }
}g;

struct Node
{
    int id, val;
    bool operator < (const Node &x) const
    {
        return val < x.val;
    }
}p[Maxn+10];

int ans;
struct Answer
{
    int x, y;

    Answer(){}
    Answer(int x, int y)
    {
        this->x = x; this->y = y;
    }
}a[10];

int main()
{
    scanf("%d%d", &n, &m);
    for(int i=1; i<=n; i++)
        p[i].id = i;
    for(int i=1; i<=m; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);

        g.AddEdge(x, y);
        g.AddEdge(y, x);

        p[x].val++; p[y].val++;
    }

    sort(p+1, p+n+1);

    if(p[n].val-p[n-1].val >= 5)
    {
        printf("ok\n");
        return 0;
    }

    int cnt = 0;
    for(int i=1; i<=n; i++)
        if(g.is_connected(p[i].id, p[n].id) == false)
        {
            a[++cnt] = Answer(p[i].id, p[n].id);
            if(cnt == 5)
                break;
        }
    
    printf("mark\n%d\n", cnt);
    for(int i=1; i<=cnt; i++)
        printf("%d %d\n", a[i].x, a[i].y);
    
    return 0;
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 0ms

memory: 1656kb

input:

output:

input:

output:

ok

result:

ok all right

Test #2:

score: 100

Accepted

time: 0ms

memory: 1592kb

input:

output:

input:

output:

ok

result:

ok all right

Test #3:

score: 100

Accepted

time: 0ms

memory: 1656kb

input:

output:

input:

output:

ok

result:

ok all right

Test #4:

score: 100

Accepted

time: 0ms

memory: 1672kb

input:

output:

input:

output:

ok

result:

ok all right

Test #5:

score: 100

Accepted

time: 0ms

memory: 1672kb

input:

output:

input:

output:

ok

result:

ok all right

Test #6:

score: 100

Accepted

time: 0ms

memory: 1684kb

input:

output:

input:

output:

ok

result:

ok all right

Test #7:

score: 100

Accepted

time: 0ms

memory: 1672kb

input:

output:

input:

output:

ok

result:

ok all right

Test #8:

score: 100

Accepted

time: 0ms

memory: 1720kb

input:

output:

input:

output:

ok

result:

ok all right

Test #9:

score: 100

Accepted

time: 0ms

memory: 1700kb

input:

output:

input:

output:

ok

result:

ok all right

Test #10:

score: 100

Accepted

time: 0ms

memory: 1660kb

input:

output:

input:

output:

ok

result:

ok all right

Test #11:

score: 100

Accepted

time: 0ms

memory: 1700kb

input:

output:

input:

output:

ok

result:

ok all right

Test #12:

score: 100

Accepted

time: 0ms

memory: 1704kb

input:

output:

input:

output:

ok

result:

ok all right

Test #13:

score: 100

Accepted

time: 0ms

memory: 1624kb

input:

output:

input:

output:

ok

result:

ok all right

Test #14:

score: 100

Accepted

time: 0ms

memory: 1648kb

input:

output:

input:

output:

ok

result:

ok all right

Test #15:

score: 100

Accepted

time: 0ms

memory: 1592kb

input:

output:

input:

output:

ok

result:

ok all right

Test #16:

score: 100

Accepted

time: 0ms

memory: 1632kb

input:

output:

input:

output:

ok

result:

ok all right

Test #17:

score: 100

Accepted

time: 0ms

memory: 1616kb

input:

output:

input:

output:

ok

result:

ok all right

Test #18:

score: 100

Accepted

time: 0ms

memory: 1672kb

input:

output:

input:

output:

ok

result:

ok all right

Test #19:

score: 100

Accepted

time: 0ms

memory: 1680kb

input:

output:

input:

output:

ok

result:

ok all right

Test #20:

score: 100

Accepted

time: 0ms

memory: 1692kb

input:

output:

input:

output:

ok

result:

ok all right

Test #21:

score: 100

Accepted

time: 0ms

memory: 1644kb

input:

output:

input:

output:

ok

result:

ok all right

Test #22:

score: 100

Accepted

time: 0ms

memory: 1672kb

input:

output:

input:

output:

ok

result:

ok all right

Test #23:

score: 100

Accepted

time: 0ms

memory: 1604kb

input:

output:

input:

output:

ok

result:

ok all right

Test #24:

score: 100

Accepted

time: 0ms

memory: 1660kb

input:

output:

input:

output:

ok

result:

ok all right

Test #25:

score: 100

Accepted

time: 0ms

memory: 1664kb

input:

output:

input:

output:

ok

result:

ok all right

Test #26:

score: 100

Accepted

time: 0ms

memory: 1708kb

input:

output:

input:

output:

ok

result:

ok all right

Test #27:

score: 100

Accepted

time: 0ms

memory: 1696kb

input:

output:

input:

output:

ok

result:

ok all right

Test #28:

score: 100

Accepted

time: 0ms

memory: 1616kb

input:

output:

input:

output:

ok

result:

ok all right

Test #29:

score: 100

Accepted

time: 0ms

memory: 1596kb

input:

output:

input:

output:

ok

result:

ok all right

Test #30:

score: 100

Accepted

time: 0ms

memory: 1664kb

input:

output:

input:

output:

ok

result:

ok all right

Test #31:

score: 100

Accepted

time: 0ms

memory: 1664kb

input:

output:

input:

output:

ok

result:

ok all right

Test #32:

score: 100

Accepted

time: 0ms

memory: 1684kb

input:

output:

input:

output:

ok

result:

ok all right

Test #33:

score: 100

Accepted

time: 0ms

memory: 1716kb

input:

output:

input:

output:

ok

result:

ok all right

Test #34:

score: 100

Accepted

time: 0ms

memory: 1628kb

input:

output:

input:

output:

ok

result:

ok all right

Test #35:

score: 100

Accepted

time: 0ms

memory: 1656kb

input:

output:

input:

output:

ok

result:

ok all right

Test #36:

score: 100

Accepted

time: 0ms

memory: 1692kb

input:

output:

input:

output:

ok

result:

ok all right

Test #37:

score: 100

Accepted

time: 0ms

memory: 1656kb

input:

output:

input:

output:

ok

result:

ok all right

Test #38:

score: 100

Accepted

time: 0ms

memory: 1624kb

input:

output:

input:

output:

ok

result:

ok all right

Test #39:

score: 100

Accepted

time: 0ms

memory: 1580kb

input:

output:

input:

output:

ok

result:

ok all right

Test #40:

score: 100

Accepted

time: 0ms

memory: 1596kb

input:

output:

input:

output:

ok

result:

ok all right

Test #41:

score: 100

Accepted

time: 0ms

memory: 1688kb

input:

output:

input:

output:

ok

result:

ok all right

Test #42:

score: 100

Accepted

time: 0ms

memory: 1660kb

input:

output:

input:

output:

ok

result:

ok all right

Test #43:

score: 100

Accepted

time: 0ms

memory: 1684kb

input:

output:

input:

output:

ok

result:

ok all right

Test #44:

score: 100

Accepted

time: 0ms

memory: 1608kb

input:

output:

input:

output:

ok

result:

ok all right

Test #45:

score: 100

Accepted

time: 0ms

memory: 1672kb

input:

output:

input:

output:

ok

result:

ok all right

Test #46:

score: 100

Accepted

time: 0ms

memory: 1660kb

input:

output:

input:

output:

ok

result:

ok all right

Test #47:

score: 100

Accepted

time: 0ms

memory: 1684kb

input:

output:

input:

output:

ok

result:

ok all right

Test #48:

score: 100

Accepted

time: 0ms

memory: 1644kb

input:

output:

input:

output:

ok

result:

ok all right

Test #49:

score: 100

Accepted

time: 0ms

memory: 1700kb

input:

output:

input:

output:

ok

result:

ok all right

Test #50:

score: 100

Accepted

time: 0ms

memory: 1696kb

input:

output:

input:

output:

ok

result:

ok all right

Test #51:

score: 100

Accepted

time: 0ms

memory: 1716kb

input:

output:

input:

output:

ok

result:

ok all right

Test #52:

score: 100

Accepted

time: 0ms

memory: 1696kb

input:

output:

input:

output:

ok

result:

ok all right

Test #53:

score: 100

Accepted

time: 0ms

memory: 1700kb

input:

output:

input:

output:

ok

result:

ok all right

Test #54:

score: 100

Accepted

time: 0ms

memory: 1700kb

input:

output:

input:

output:

ok

result:

ok all right

Test #55:

score: 100

Accepted

time: 0ms

memory: 1716kb

input:

output:

input:

output:

ok

result:

ok all right

Test #56:

score: 100

Accepted

time: 0ms

memory: 1668kb

input:

output:

input:

output:

ok

result:

ok all right

Test #57:

score: 100

Accepted

time: 0ms

memory: 1700kb

input:

output:

input:

output:

ok

result:

ok all right

Test #58:

score: 100

Accepted

time: 0ms

memory: 1676kb

input:

output:

input:

output:

ok

result:

ok all right

Test #59:

score: 100

Accepted

time: 0ms

memory: 1700kb

input:

output:

input:

output:

ok

result:

ok all right

Test #60:

score: 100

Accepted

time: 0ms

memory: 1628kb

input:

output:

input:

output:

ok

result:

ok all right

Test #61:

score: 100

Accepted

time: 0ms

memory: 1696kb

input:

output:

input:

output:

ok

result:

ok all right

Test #62:

score: 100

Accepted

time: 0ms

memory: 1680kb

input:

output:

input:

output:

ok

result:

ok all right

Test #63:

score: 100

Accepted

time: 0ms

memory: 1668kb

input:

output:

input:

output:

ok

result:

ok all right